Олимпиадная математика. Комбинаторика. В ряд лежат a+b пронумерованных коробок, причём в первых a коробках лежит по одному яблоку, а в последних b коробках — по одной груше. За один ход разрешается одновременно переложить яблоко из коробки с номером i в коробку с номером i+1, а грушу из коробки с номером j в коробку с номером j−1, если разность i−j чётная (i и j не обязательно различны). При этом в коробках может оказаться больше одного фрукта. Нужно добиться того, чтобы в первых b коробках оказалось по одной груше, а в последних a коробках — по одному яблоку. Докажите, что это можно сделать тогда и только тогда, когда произведение ab — чётное.

Предыдущий
вопрос Следующий
вопрос

Для начала заметим, что если произведение ab чётное, то либо a, либо b чётное. Без ограничения общности, будем считать, что a чётное число.

Пусть, напротив, произведение ab нечётное. Тогда и a, и b - нечётные числа. Заметим, что после каждого хода сумма номеров коробок с яблоками и грушами изменяется на чётную величину (либо увеличивается на 2, либо уменьшается на 2). Поскольку и a, и b нечётные, то после любого количества ходов сумма будет иметь ту же чётность, что и в начале. Но изначально сумма равна a + b, которое нечётное. Следовательно, невозможно привести коробки к требуемому виду, при условии, что произведение ab нечётное.

Теперь докажем обратное утверждение. Если ab - чётное, то можем представить, что a - чётное, b - нечётное (или наоборот, так как результат будет аналогичным). Заметим, что общая нечётность суммы номеров коробок с яблоками и грушами сохраняется после каждого хода. Но тогда, после некоторого количества ходов, сумма станет чётной (что и требуется). Следовательно, если ab чётное, то можно привести коробки к требуемому виду.

Таким образом, это можно сделать тогда и только тогда, когда произведение ab - чётное.