У літній школі для юних математиків та програмістів вожаті вирішили провести логічну гру для всіх учнів, яких було рівно 1024. Діти домовились у цей день, що кожний або говорить правду, або бреше, та протягом дня не змінюють своєї ролі. Вожаті розкреслили на асфальті квадрат 32х32, у кожній комірці розташувався один учень. Потім кожний із них сказав: «Серед моїх сусідів більше половини – брехуни». Сусідніми вважаються комірки зі спільною стороною. Вожаті Микола та Сашко вирішили заохотити призами усіх правдивих за любов до істини. Знайдіть найменшу кількість призів, що їм треба купити, щоб гарантовано вистачило на всіх правдивих. Відповідь обґрунтуйте.

Відповідь:

Покрокове пояснення: Позначимо 1 тих учнів, які говорять правду і 0 – тих, хто бреше. Тоді заява кожного учня може бути переписана як «серед чотирьох сусідів мене брешуть хоча б двоє». Розглянемо комірку, що знаходиться в середині квадрата 32х32. Вона має 4 сусіди з-за кожного з яких можуть бути 2 варіанти: або сусід говорить правду, або бреше. Загалом, у нас є 4 сусіди, кожен з яких може говорити правду або брехати, тому всього може бути $2^4=16$ можливих комбінацій. Проте серед них тільки дві вірні (тобто такі, коли хоча б двоє з чотирьох сусідів говорять правду): 0110 і 1001. Це означає, що серед чотирьох сусідів комірки, тільки в двох випадках може бути правдивим той учень, який знаходиться в комірці. Таким чином, ми довели, що неможливо, щоб більш як половина учнів говорила правду.

Припустимо, що в нашому квадраті було $x$ правдивих учнів. Тоді кожен з них має не більше двох сусідів-брехунів, або ж жодних таких сусідів. Таким чином, кількість учнів-брехунів не може перевищувати кількість учнів-правдивців. Отже, $x+x/2 \leq 1024$, звідки $x\leq 684$.

Тому найбільша можлива кількість правдивих учнів – 684. Щоб забезпечити, що всі вони отримають призи, необхідно купити щонайменше 684 призів.