|
|
 |
Условие
В школе решили провести турнир по настольному теннису между математическими и гуманитарными классами. Команда гуманитарных классов состоит из n человек, команда математических – из m, причём n ≠ m. Так как стол для игры всего один, было решено играть следующим образом. Сначала какие-то два ученика из разных команд начинают играть между собой, а все остальные участники выстраиваются в одну общую очередь. После каждой игры человек, стоящий в очереди первым, заменяет за столом члена своей команды, который становится в конец очереди. Докажите, что рано или поздно каждый математик сыграет с каждым гуманитарием.
Решение
Пронумеруем отдельно гуманитариев и отдельно математиков в порядке, определённом исходной очередью (в первой партии играют М1 и Г1). Заметим, что математики (гуманитарии) отдельно (считая того, кто за столом) всегда находятся в очереди в том же циклическом порядке: никто друг друга не обгоняет. Математик может сместиться в очереди относительно гуманитария, но только за столом: например, математик М может выйти к столу раньше гуманитария Г, а выйти из-за стола позже него.
Разобьём все игры на циклы по m + n − 2 игры. За время первого цикла из-за стола выйдут m + n − 2 игрока, то есть все стоящие в очереди, кроме Мm и Гn. Значит, они стоят за столом в начале второго цикла. По тем же соображениям в начале третьего цикла за столом стоят Мm–1 и Гn–1, и т. д.: с каждым циклом номера играющих в его первой партии смещаются "по кругу" на 1. Поэтому каждый математик за m циклов выйдет из-за стола ровно m − 1 раз, а за mn циклов – n(m − 1) раз. Аналогично каждый гуманитарий за mn циклов выйдет из-за стола ровно m(n − 1) раз.
Пусть, например, m > n. Тогда n(m − 1) – m(n − 1) = m – n ≥ 1. Рассмотрим произвольных математика М и гуманитария Г. Как показано выше, за 2mn циклов М выходил из-за стола по крайней мере на два раза больше, чем Г. Отсюда следует, что между какими двумя "выходами" М у Г выходов из-за стола не было. Допустим, Г ни разу не сыграл с М. Тогда Г между этими выходами М оставался в очереди. Но после первого выхода он был впереди М, а когда М снова дошёл до стола – позади него. Противоречие, так как Г не мог обогнать М в очереди.
Замечания
1. На самом деле каждая пара противников сыграет между собой уже за mn циклов. Действительно, если m и n взаимно просты, то, как видно из вышеизложенного, они встретятся за столом в первой партии одного из циклов. В противном случае |m – n| ≥ 2, и конец доказательства проходит уже для mn циклов.
2. При n = m > 2 утверждение неверно. Например, если математики будут чередоваться с гуманитариями, то каждый всегда будет играть только со своими соседями по кругу, порядок в котором меняться не будет.
3. 9 баллов.
