Поиск знаменитости (общий случай)

Как-то про 8 человек все слишком просто...

Назовем участника компании знаменитостью, если его знают все остальные в этой компании, а он не знает никого из остальных.

В компании N=2^k человек. Обратившись к любому из них, мы можем задать ему вопрос вида "Знаете ли Вы такого-то?" и получить ответ. Пользуясь такими вопросами, мы хотим выяснить, есть ли в этой компании знаменитость, и если да, то найти ее.
а) Докажите, что хватает 3N-k-3 вопросов
б)* Докажите, что 3N-k-4 вопросов может не хватить.