Олимпиадные задачи по теме «Вспомогательная раскраска»

Куб с ребром <i>n</i> составлен из белых и чёрных кубиков с ребром 1 таким образом, что каждый белый кубик имеет общую грань ровно с тремя чёрными, а каждый чёрный – ровно с тремя белыми. При каких <i>n</i> это возможно?

На поверхности куба проведена замкнутая восьмизвенная ломаная, вершины которой совпадают с вершинами куба.

Какое наименьшее количество звеньев этой ломаной может совпасть с рёбрами куба?

Шесть кружков последовательно соединили отрезками. На каждом отрезке записали некоторое число, а в каждом кружке – сумму двух чисел, записанных на входящих в него отрезках. После этого стёрли все числа на отрезках и в одном из кружков (см. рис.). Можно ли найти число, стёртое в кружке?<div align="center"><img src="/storage/problem-media/116854/problem_116854_img_2.gif"></div>

В клетках квадрата 3×3 расставлены числа (рис. слева). Разрешается к числам, стоящим в двух соседних клетках, одновременно прибавлять одно и то же число, <i>не обязательно положительное</i>. Можно ли в какой-то момент получить такой квадрат с числами, как на рисунке справа? (Клетки считаются соседними, если имеют общую сторону.)<div align="center"><img src="/storage/problem-media/116845/problem_116845_img_2.gif"></div>

Назовём компанию <i>k-неразбиваемой</i>, если при любом разбиении её на <i>k</i> групп в одной из групп найдутся два знакомых человека. Дана 3-неразбиваемая компания, в которой нет четырёх попарно знакомых человек. Докажите, что её можно разделить на две компании, одна из которых 2-неразбиваемая, а другая – 1-неразбиваемая.

В некоторых клетках доски 100×100 стоит по фишке. Назовём клетку <i>красивой</i>, если в соседних с ней по стороне клетках стоит чётное число фишек.

Может ли ровно одна клетка доски быть красивой?

На доске нарисован выпуклый 2011-угольник. Петя последовательно проводит в нём диагонали так, чтобы каждая вновь проведённая диагональ пересекала по внутренним точкам не более одной из проведённых ранее диагоналей. Какое наибольшее количество диагоналей может провести Петя?

Дан квадрат <i>n</i>×<i>n</i>. Изначально его клетки раскрашены в белый и чёрный цвета в шахматном порядке, причём хотя бы одна из угловых клеток чёрная. За один ход разрешается в некотором квадрате 2×2 одновременно перекрасить входящие в него четыре клетки по следующему правилу: каждую белую перекрасить в чёрный цвет, каждую чёрную – в зелёный, а каждую зелёную – в белый. При каких <i>n</i> за несколько ходов можно получить шахматную раскраску, в которой чёрный и белый цвета поменялись местами?

Какое наименьшее количество клеток требуется отметить на шахматной доске, чтобы каждая клетка доски (отмеченная или неотмеченная) граничила по стороне хотя бы с одной отмеченной клеткой?

Какое наибольшее количество клеток можно отметить на шахматной доске так, чтобы с каждой из них на любую другую отмеченную клетку можно было пройти ровно двумя ходами шахматного коня?

На некоторых клетках доски 10×10 сидит по блохе. Раз в минуту блохи одновременно прыгают, причём каждая – в соседнюю клетку (по стороне). Блоха прыгает строго в одном из четырёх направлений, параллельных сторонам доски, сохраняет направление, пока это возможно, иначе меняет его на противоположное. Пес Барбос наблюдал за блохами в течение часа и ни разу не видел, чтобы две из них сидели на одной клетке. Какое наибольшее количество блох могло прыгать по доске?

Деревянный брусок тремя распилами распилили на восемь меньших брусков. На рисунке у семи брусков указана их площадь поверхности.

Какова площадь поверхности невидимого бруска?

<center><i> <img align="absmiddle" src="/storage/problem-media/116065/problem_116065_img_2.gif"> </i></center>

Квадратная доска разделена на <i>n</i>² прямоугольных клеток  <i>n</i> – 1  горизонтальными и  <i>n</i> – 1  вертикальными прямыми. Клетки раскрашены в шахматном порядке. Известно, что на одной диагонали все <i>n</i> клеток чёрные и квадратные. Докажите, что общая площадь всех чёрных клеток доски не меньше общей площади белых.

Концы <i>N</i> хорд разделили окружность на 2<i>N</i> дуг единичной длины. Известно, что каждая из хорд делит окружность на две дуги чётной длины.

Докажите, что число <i>N</i> чётно.

В пифагоровой таблице умножения выделили прямоугольную рамку толщиной в одну клетку, причём каждая сторона рамки состоит из нечётного числа клеток. Клетки рамки поочередно раскрасили в два цвета – чёрный и белый. Докажите, что сумма чисел в чёрных клетках равна сумме чисел в белых клетках.

Пифагорова таблица умножения – это клетчатая таблица, в которой на пересечении <i>m</i>-й строки и <i>n</i>-го столбца стоит число <i>mn</i> (для любых натуральных <i>m</i> и <i>n</i>).

В некоторых клетках квадрата 20×20 стоит стрелочка в одном из четырёх направлений. На границе квадрата все стрелочки смотрят вдоль границы по часовой стрелке (см. рис.). Кроме того, стрелочки в соседних (возможно, по диагонали) клетках не смотрят в противоположных направлениях. Докажите, что найдётся клетка, в которой стрелочки нет. <div align="center"><img src="/storage/problem-media/115497/problem_115497_img_2.gif"> </div>

На столе в виде треугольника выложены28монет одинакового размера (рис.). Известно, что суммарная масса любой тройки монет, которые попарно касаются друг друга, равна10 г. Найдите суммарную массу всех18 монет на границе треугольника.

<center><i> <img align="absmiddle" src="/storage/problem-media/115493/problem_115493_img_2.gif"> </i></center>

Восемь клеток одной диагонали шахматной доски назовём забором. Ладья ходит по доске, не наступая на одну и ту же клетку дважды и не наступая на клетки забора (промежуточные клетки не считаются посещёнными). Какое наибольшее число прыжков через забор может совершить ладья?

Двое играют на треугольной доске (см. рис.), закрашивая по очереди на ней треугольные клеточки. Одна клетка (начальная) уже закрашена перед началом игры. Первым ходом закрашивается клеточка, граничащая (по стороне) с начальной, а каждым следующим ходом — клетка, граничащая с только что закрашенной. Повторно клетки красить нельзя. Тот, кто не может сделать ход, проигрывает. Кто — начинающий или его соперник — победит в этой игре, как бы ни играл его партнёр? Рассмотрите случаи: а) Начальная клетка — угловая, поле любого размера; б) Поле и начальная клетка как на рисунке к этому заданию; в) Общий случай: поле любого размера, и начальная клетка в нём произвольная. г)<b>Дополнительное задание.</b>Можно подумать, что начальная клетка определяет исход партии независимо от действий иг...

На краю круглого вращающегося стола через равные промежутки стояли 30 чашек с чаем. Мартовский Заяц и Соня сели за стол и стали пить чай из каких-то двух чашек (не обязательно соседних). Когда они допили чай, Заяц повернул стол так, что перед каждым опять оказалось по полной чашке. Когда и эти чашки опустели, Заяц снова повернул стол (возможно на другой угол), и снова перед каждым оказалась полная чашка. И так продолжалось до тех пор, пока весь чай не был выпит. Докажите, что если бы Заяц всегда поворачивал стол так, чтобы его новая чашка стояла через одну от предыдущей, то им бы тоже удалось выпить весь чай (то сеть тоже каждый раз обе чашки оказывались бы полными).

Любознательный турист хочет прогуляться по улицам Старого города от вокзала (точка <i>A</i> на плане) до своего отеля (точка <i>B</i>). Турист хочет, чтобы его маршрут был как можно длиннее, но дважды оказываться на одном и том же перекрестке ему неинтересно, и он так не делает. Нарисуйте на плане самый длинный возможный маршрут и докажите, что более длинного нет. <div align="center"><img align="absmiddle" src="/storage/problem-media/111897/problem_111897_img_2.gif"></div>

В квадрате 10×10 расставлены числа от 1 до 100: в первой строчке – от 1 до 10 слева направо, во второй – от 11 до 20 слева направо и т.д. Андрей собирается разрезать квадрат на доминошки 1×2, посчитать произведение чисел в каждой доминошке и сложить полученные 50 чисел. Он стремится получить как можно меньшую сумму. Как ему следует разрезать квадрат?

В каждой вершине выпуклого 100-угольника написано по два различных числа. Докажите, что можно вычеркнуть по одному числу в каждой вершине так, чтобы оставшиеся числа в каждых двух соседних вершинах были различными.

Грани куба 9×9×9 разбиты на единичные клетки. Куб оклеен без наложений бумажными полосками 2×1 (стороны полосок идут по сторонам клеток). Докажите, что число согнутых полосок нечётно.

На шахматной доске расставлены во всех клетках 32 белых и 32 черных пешки. Пешка может бить пешки противоположного цвета, делая ход по диагонали на одну клетку и становясь на место взятой пешки (белые пешки могут бить только вправо-вверх и влево-вверх, а чёрные – только влево-вниз и вправо-вниз). Другим образом пешки ходить не могут. Какое наименьшее количество пешек может остаться на доске?