سلام حالت n/2 رو که غلیظ گفت. برای این که بگیم روشی وجود نداره که همیشه بیشتر از نصف آدما درست بگن، میایم امید ریاضی تعداد درست گفتن ها رو حساب می کنیم.
$c_i$ رو میگیریم متغیر تصادفی درست گفتن آیمین نفر. (درست بگه ۱ه، غلط بگه ۰ه)
$C$ رو هم میگیریم متغیر تصادفی تعداد درست گفتن ها
$C = \Sigma c_i$
در نتیجه : $E(C) = \Sigma E(c_i)$
هر کسی توی نصف $2^{n}$ حالت ممکن درست می گه. چون به ازای هر دو حالتی که توشون فقط رنگ کلاه خودش فرق می کنه،دقیقا توی یکیش درست می گه. در نتیجه : $\forall i : E(c_i) = \frac{1}{2}$
و $E(C) = \Sigma c_i = \frac{n}{2}$
پس امید ریاضی درست گفتن ها نصف تعداد افراده. در نتیجه همیشه یه حالتی وجود داره که توش حداکثر نصف افراد درست می گن. با راه غلیظ یه کاری می کنیم که همیشه دقیقا نصف افراد درست بگن!

جواب کف n/2 است . به این صورت که جفت جفت کنیم و هر یکی رنگ مخالف کلاه جفتش و یکی دیگر رنگ موافق کلاه جفتش رو بگه. واضح است که از هر جفت حداقل یک جواب درست به دست می اید.

حال اثبات بهینگی آن :

کافی است که یک چینشی از رنگ کلاه ها بیاوریم که در ان جداکثر n/2 تا درست بتوان گفت . برای اینکار از روش میانگین گیری استفاده می کنیم. به این صورت : یک گراف دوبخشی می سازیم که در قسمت بالایی شامل $2^n$ تا راس است که هر یک معرف یک چیدمان کلاه ها هست . در قسمت پایین هم n تا راس وجود دارد که هریک معرف یک نفر است. هر نفر را به یک چیدمان وصل میکنیم اگر آن نفر در ان چیدمان برنده باشد. خب از اون جایی که نمی توانند با هم حرف بزنند پس ان با توجه به n-1 نفر دیگر راجع به رنگش خودش نظر میدهد و اگر رنگ کلاه n-1 نفر دیگر را عوض نکنیم و فقط رنگ اون شخص را عوض کنیم جواب اون شخص فرقی نمیکند. پس این فرد در نصف چیدمان ها جواب درست می دهد. پس درجه هر راس از پایین 2^(n-1) است پس سرجمع n*2^n-1 یال از پایین به بالا می رود . پس طبق اصل لانه کبوتری راسی در بالا پیدا می شود که درجه اش کف n/2 است . پس حکم ثابت شد . یعنی چیدمانی از رنگ ها پیدا می شود که در ان حداکثر n/2 تا برنده وجود دارد. و از طرفی هم الگوریتم n/2 را اثبات کردیم . پس بهینگی جواب اثبات شد :)

نفرات رو 2 تا 2 تا جفت کن مثلا جفت A, B A همیشه رنگ کلاه B رو برای خودش بگه و B همیشه عکس رنگ کلاه A رو بگه. 4 حالت داره که رنگ کلاه A , B چه رنگی باشه ، راحت قابل بررسی هست که در هر نوبت یکی حداقل درست میگه . پس جواب میشه کف n/2 حالا بازم میگم مطمئن نیستم که از کف n/2 بیشتر میشه یا نه !!

n-1 نفر.

قبل از مسابقه باید افراد توافق کنن که به نوبت جواب بدن.

حالا نفر اول میاد به کلاه ها نگاه می کنه و اگه تعداد فردی کلاه قرمز وجود داشت میگه قرمز وگرنه میگه آبی.

دیگران با توجه به رنگ کلاهش و پیروز شدن یا نشدن اون رنگ گفته شده توسط اون رو میفهمن.

حالا میدونن که به غیر اون در بین افران تعداد کلاه های قرمز فرده یا زوج.

و از این طریق همشون میتونن رنگ کلاه خودشونو تشخیص بدن.

پس جواب: n-1 نفر.

≈≈≈≈≈≈پ.ن: (توضیح برای خط چهارم):

نفری که میخواد جواب بده رنگ کلاه نفر قبلی رو میدونه، میبینه که آیا نفر قبلی برنده شد یا نه.

مثلا: اگه برنده شد و رنگ کلاهش هم قرمز بود نتیجه میگیره که اون رنگ قرمز رو اعلام کرده بوده.

به همین ترتیب 4 حالت وجود داره و این فرد میتونه با توجه به اون حالت ها رنگ کلاه نفر قبلی و در نتیجه زوجیت تعداد کلاه های قرمز رو تشخیص بده.