مساله ۲. ده عکس

۱۰ قاب عکس داریم که توی هر کدوم از اونها سه نفر حضور دارن. در همه عکس ها نفر سمت چپی پدر و نفر سمت راستی عموی نفر وسط هستند. همچنین نفر سمت چپ عکس ها ۱۰ نفر متفاوت هستند. حداقل چند نفر در مجموع این ۱۰ عکس حضور دارن؟

لینک مساله در توویتر: https://twitter.com/Riazi_Cafe/status/1663699752070905856

جواب درست ۱۶ ه. برای اثبات این، اول باید نشون بدیم که با ۱۶ نفر میشه ۱۰ عکس ساخت و با کمتر از ۱۶ تا نمی‌شه ساخت.

همونطور که بعضی از دوستان اشاره کردن با ۱۶ نفر میشه ساخت، مثل حالتی که این دوستمون گذاشته: https://twitter.com/AliAbdi_fa/status/1663881857862193153

حالا بررسی می‌کنیم که چرا با کمتر از ۱۶ نفر نمی‌شه ساخت.

فرض کنین: a = تعداد کسانی که در عکسا پدر یا عمو نبودن و فقط پسر بودن b = تعداد کسانی که در عکسا پدر بودن، عمو نبودن c = تعداد کسانی که در عکسا عمو بودن، پدر نبودن d = تعداد کسانی که در عکسا هم عمو بودن و هم پدر

تعداد کل افراد در عکس‌ها میشه جمع این ۴ عدد.

میشه ثابت کرد \[a >= \frac{d}{2} + 1\]

و چون ۱۰ عکس داریم که ۲۰ عمو و پدر توش هست، \[b + c + 2d = 20\] از کنار هم گذاشتن ۲ رابطه بالا نتیجه می‌گیریم \[a + b + c + d >= 21 - \frac{d}{2}\] و چون ۱۰ عکس داریم، d حداکثر ۱۰ ه، و پس \[a + b + c + d >= 16\].

لینک راه‌حل در توویتر: https://twitter.com/Riazi_Cafe/status/1664832603759824897