Мышь грызет кусочек сыра в форме куба с ребром 3, разбитый на 27 единичных кубиков. Когда она съедает какой-то кубик, то переходит к следующему, который имеет общую грань с предыдущим. Может ли мышь скушать весь кусок сыра, кроме центрального единичного кубика?

Указание: Используйте метод раскрасок, а именно следующий способ:

Решение: Воспользуемся способом раскраски и поскрасим единичные кубики в два цвета через один, следующим образом:

У нас 27 кубиков. Чтобы скушать все кубики сыра, кроме центрального, придется съесть 26 кусочков. Причем, половину будет белого цвета, половина - черного (так как мышь ест соседние кубики, которые имеют разный цвет). Но это невозможно, т.к. с другой стороны, у нас всего 15 белых кубиков и 14 черных (благодаря раскраске). И если мышь не будет кушать центральный, то будет съедено 15 белых и 13 черных, так как центральный кубик - черного цвета.

Дно прямоугольной коробки было выложено прямоугольными плитками 2 x 2 и 1 x 4. Плитки высыпали из коробки и при этом потеряли плитку размером 2 x 2. Вместо нее нашли плитку размером 1 x 4. Можно ли при этом выложить дно коробки?

Указание: Используйте метод раскраски следующим образом:

Ответ: Нет, нельзя. Используя метод раскраски, раскрасим дно коробки следующим образом:

Плитка 2 x 2 покрывает лишь одну черную клетку. Плитка 1 x 4 покрывает или две и ни одну черную. То есть четность покрытых черных клеток совпадает с четностью количества плиток размером 2 x 2. Потому при потере плитки 2 x 2 останется лишь одна незакрашенная черная клетка. Замена невозможна.

На клетчатой бумаге даны произвольные n клеток (n > 4). Докажите, что из них можно выбрать не менее [ⁿ/₄] клеток, не имеющих общих точек.

Указание: Воспользуйтесь методом раскраски следующим образом (используя четыре цвета):

Ответ: Воспользуемся методом раскрасок и покрасим клетки в четыре цвета следующим образом:

Тогда, по принципу Дирихле, среди n клеток, можно выбрать [ⁿ/₄] клеток одного цвета. А так как клетки одного цвета не имеют общих точек, то утверждение доказано.