Question

Имеется 100 дискеток и 100 этикеток, раскрашенные в два цвета. Дубль это дискета, к которой приклеена этикетка того же цвета. Докажите, что можно добиться того, что все дубли будут одного цвета?

Answer 1

Ответ:

Наклеим сначала этикетки на дискетки в произвольном порядке. Предположим, что у нас образовались дубли нескольких различных цветов. Возьмем по одной дискетке-дублю двух разных цветов и обменяем их этикетки. После этого каждая из дискеток перестанет быть дублем, так что общее число дублей уменьшится на 2. Далее будем повторять эту операцию до тех пор, пока дублей различных цветов не останется.2. Докажем нужный факт индукцией по числу дискеток (при этом можно даже не обращать внимание на соответствие цветов дискеток и этикеток!) . База индукции (одна дискетка) очевидна. Переход: если все k + 1 дискеток одноцветны, то и доказывать нечего. Если же есть дискетки разных цветов, то возьмем одну из них и наклеим на нее этикетку другого цвета, а для остальных k дискеток применим предположение индукции.

Answer 2

Давайте рассмотрим данную проблему методом математической индукции.

Базовый случай: При 1 дискете и 1 этикетке нечего менять, так как они будут иметь одинаковый цвет.

Шаг индукции: Предположим, что мы имеем некоторое количество дискеток и этикеток, и среди них уже есть хотя бы одна пара дублей одного цвета. Теперь добавим одну дискету и одну этикетку, таким образом у нас будет 101 дискета и 101 этикетка.

Существует два случая:

1. Новая дискета имеет тот же цвет, что и новая этикетка. В этом случае мы получили еще одну пару дублей одного цвета.

2. Новая дискета имеет цвет, отличный от цвета новой этикетки. Теперь у нас есть 100 дублей одного цвета среди оставшихся дискет и этикеток (по предположению индукции), и у нас есть одна дискета и одна этикетка нового цвета. Мы можем взять одну из оставшихся дублей того же цвета, поменять с ней новую дискету, а новую этикетку поменять с той дискетой, которая не является дублем. Таким образом, мы создаем еще одну пару дублей одного цвета.

Таким образом, независимо от того, какой случай произойдет при добавлении новой дискеты и этикетки, мы всегда получим еще одну пару дублей одного цвета. По индукции, это означает, что после добавления всех 100 дополнительных дискет и этикеток у нас будет 100 пар дублей одного цвета.