Решение задачи: Закраска клеток прямоугольника без соседних

Задание 1

Условие: На доске нарисован клетчатый прямоугольник \(2 \times 100\). Будем считать две клетки соседними, если они имеют общую сторону. Сколькими способами можно закрасить ровно 99 клеток так, чтобы среди них не было соседних?

Решение:

1. Анализ условия:

   • У нас есть прямоугольник размером \(2 \times 100\). Общее количество клеток в нем равно \(2 \times 100 = 200\).
   • Нам нужно закрасить ровно 99 клеток.
   • Условие "соседние клетки" означает, что клетки, имеющие общую сторону (вертикальную или горизонтальную), не должны быть закрашены одновременно. Это похоже на задачу о раскраске шахматной доски.

2. Шахматная раскраска:
   Если мы раскрасим доску в стиле шахматной доски (чередуя цвета, например, черный и белый), то каждая клетка будет иметь соседей только противоположного цвета.
   В прямоугольнике \(2 \times 100\) всего 200 клеток. При шахматной раскраске будет 100 клеток одного цвета (например, белых) и 100 клеток другого цвета (например, черных).

3. Применение условия к шахматной раскраске:
   Если мы закрасим все клетки одного цвета (например, все белые), то ни одна из закрашенных клеток не будет соседней с другой закрашенной клеткой, так как все соседи белой клетки — черные, и наоборот.
   В нашем случае, если мы закрасим все 100 белых клеток, условие "среди них не было соседних" будет выполнено. Аналогично, если мы закрасим все 100 черных клеток.

4. Рассмотрение количества закрашиваемых клеток:
   Нам нужно закрасить ровно 99 клеток.

   • Если мы выберем для закрашивания клетки одного цвета (например, белые), то мы можем выбрать любые 99 из 100 белых клеток. Количество способов выбрать 99 клеток из 100 равно числу сочетаний \(C(100, 99)\).
   • \(C(n, k) = \frac{n!}{k!(n-k)!}\).

   • \(C(100, 99) = \frac{100!}{99!(100-99)!} = \frac{100!}{99!1!} = \frac{100 \times 99!}{99!} = 100\).
     Таким образом, есть 100 способов выбрать 99 белых клеток.

   • Аналогично, есть 100 способов выбрать 99 черных клеток из 100 черных клеток.

5. Общее количество способов:
   Так как мы можем закрасить 99 белых клеток ИЛИ 99 черных клеток, общее количество способов равно сумме способов для каждого цвета.
   Общее количество способов = (способы закрасить 99 белых) + (способы закрасить 99 черных) = \(100 + 100 = 200\).

Ответ: 200 способов.