Версия для печати
Убрать все задачи
В турнире участвовало 11 шахматистов: 4 – из России и 7 зарубежных. Каждый шахматист сыграл с каждым по две партии (выигрыш – 1 очко, ничья – 0,5 очка, поражение – 0). По окончании турнира оказалось, что все участники набрали различное количество очков, причем сумма очков, набранных россиянами, равна сумме очков, набранных иностранцами. Могло ли в тройке призеров не оказаться ни одного россиянина?

Решение
В ряд слева направо стоят $N$ коробок, занумерованных подряд числами $1$, $2, \ldots, N$.
В некоторые коробки, стоящие подряд, положат по шарику, оставив остальные пустыми.
Инструкция состоит из последовательно выполняемых команд вида «поменять местами содержимое коробок № $i$ и № $j$», где $i$ и $j$ – числа. Для каждого ли $N$ существует инструкция, в которой не больше $100N$ команд, со свойством: для любой начальной раскладки указанного вида можно будет, вычеркнув из инструкции некоторые команды, получить инструкцию, после выполнения которой все коробки с шариками будут левее коробок без шариков?

Решение