Сюжет 2
Шары с номерами от 1 до 800 поровну разложены по N сосудам неизвестным фокуснику образом. Он отдает команды вида «поменяйте шары с номерами i и j», после чего ассистент меняет их, если они и вправду в разных сосудах (иначе ничего не происходит). После нескольких команд фокусник останавливается.
2.2 Пусть N = 400. Докажите, что фокусник может добиться того, чтобы гарантированно более половины шаров лежали не в своём сосуде.
Разобьем почти все шары на тройки. В каждой тройке (a, b, c) прикажем поменять сначала a с b, потом b с c. Если все они были в разных сосудах, то все они поменяют сосуд, если два из них были в одном сосуде, то поменяют сосуд два из трёх (например, можно разобрать все три случая). В итоге поменяется сильно больше половины шаров (почти две трети).
—