Есть доска 1×1000, вначале пустая, и куча из n фишек. Двое ходят по очереди. Первый своим ходом "выставляет" на доску не более 17 фишек по одной на любое свободное поле (он может взять все 17 из кучи, а может часть – из кучи, а часть – переставить на доске). Второй снимает с доски любую серию фишек (серия – это несколько фишек, стоящих подряд, то есть без свободных полей между ними) и кладёт их обратно в кучу. Первый выигрывает, если ему удастся выставить все фишки в ряд без пробелов.
  а) Докажите, что при  n = 98  первый всегда может выиграть.
  б) При каком наибольшем n первый всегда может выиграть?

   Решение

Даны окружность и точка A. Найдите геометрическое место середин хорд, высекаемых данной окружностью на всевозможных прямых, проходящих через точку A.

   Решение

Диагональ BD четырёхугольника ABCD является диаметром окружности, описанной около этого четырёхугольника. Найдите диагональ AC, если BD = 2, AB = 1, ABD : DBC = 4 : 3.

   Решение

Дано натуральное число  n ≥ 2.  Рассмотрим все такие покраски клеток доски n×n в k цветов, что каждая клетка покрашена ровно в один цвет и все k цветов встречаются. При каком наименьшем k в любой такой покраске найдутся четыре окрашенных в четыре разных цвета клетки, расположенные в пересечении двух строк и двух столбцов?

   Решение

Темы:    [ Числовые таблицы и их свойства ] [ Раскраски ] [ Примеры и контрпримеры. Конструкции ] [ Теория графов (прочее) ] [ Принцип крайнего (прочее) ] [ Индукция (прочее) ]

Сложность: 4+ Классы: 9,10,11

Прислать комментарий

Условие

Дано натуральное число  n ≥ 2.  Рассмотрим все такие покраски клеток доски n×n в k цветов, что каждая клетка покрашена ровно в один цвет и все k цветов встречаются. При каком наименьшем k в любой такой покраске найдутся четыре окрашенных в четыре разных цвета клетки, расположенные в пересечении двух строк и двух столбцов?

Решение

  Сначала покажем, как покрасить клетки в  2n – 1  цвет так, чтобы не было ни одной четвёрки клеток разных цветов, лежащих на пересечении двух горизонталей и двух вертикалей.
  Первый способ. Занумеруем горизонтальные ряды сверху вниз чётными числами 0, 2, 4, ...,  2n – 2,  а вертикальные ряды слева направо нечётными числами 1, 3, ...,  2n – 1.  Покрасим последовательно 0-й ряд в цвет 0, 1-й ряд – в цвет 1, ..., (2n–1)-й ряд – в цвет  2n – 1.  При этом при покраске очередного ряда мы перекрашиваем все клетки, которые были покрашены ранее. В конечной раскраске присутствует  2n – 1  цвет (цвета 0 не останется).
  Рассмотрим четыре клетки на пересечении двух горизонталей и двух вертикалей. Один из этих четырёх рядов (вертикалей или горизонталей) был покрашен последним; тогда две его клетки останутся окрашенными в этот цвет и, следовательно, будут одноцветными.
  Второй способ. Покрасим все клетки первой горизонтали H и первой вертикали V в  2n – 1  различный цвет, причём клетку на их пересечении покрасим в цвет c; затем покрасим все оставшиеся клетки также в цвет c. Тогда из четырёх клеток на пересечении любых двух столбцов и двух строк максимум две будут иметь цвет, отличный от c.

  Докажем, что при  k ≥ 2n  требуемая четвёрка обязательно найдётся.
  Первый способ. Рассмотрим раскраску клеток в 2n или более цветов. Переформулируем задачу следующим образом. Рассмотрим двудольный граф, вершины которого соответствуют горизонталям и вертикалям доски (всего 2n вершин). Если клетка на пересечении некоторых горизонтали и вертикали покрашена в цвет c, то соединим вершины, соответствующие этим горизонтали и вертикали, ребром цвета c. Разноцветным циклом будем называть цикл, в котором нет двух рёбер одного цвета. Нам требуется доказать, что в построенном графе найдется разноцветный цикл из 4 рёбер.
  Докажем, что найдётся разноцветный цикл (возможно, более чем из четырёх рёбер). Выберем по одному ребру каждого цвета – всего не менее 2n рёбер попарно разных цветов. Остальные рёбра временно сотрём. В полученном графе количество рёбер не меньше количества вершин; как известно, в таком графе найдется цикл.
  Теперь найдём в исходном графе кратчайший разноцветный цикл. Пусть это цикл a₁b₁a₂b₂...a_sb_sa₁ из 2s ребер, где a_i – вершины, соответствующие горизонталям доски, а b_j – вершины, соответствующие вертикалям. Пусть  s > 2.  Рассмотрим ребро b₂a₁. Если его цвет отличен от цвета каждого из ребер a₁b₁, b₁a₂ и a₂b₂, то a₁b₁a₂b₂a₁ – разноцветный цикл из 4 рёбер; противоречие. Значит, цвет ребра b₂a₁ отличен от цвета каждого из ребер b₂a₃, a₃b₃, ..., a_kb_k, b_ka₁, тем самым цикл a₁b₂a₃b₃...a_kb_ka₁ из 2k – 2 ребер является разноцветным; противоречие.
  Второй способ. Индукцией по  m + n  докажем более общее утверждение: если клетки прямоугольника m×n окрашены в  k ≥ m + n  цветов, причём все цвета присутствуют, то найдутся 4 разноцветных клетки на пересечении двух строк и двух столбцов.
  При  m = 1  утверждение верно, ибо раскрасок n клеток в  n + 1  цвет не существует; в частности, это доказывает базу индукции при
m + n = 2.
  Шаг индукции. Пусть  m, n ≥ 2.  Назовём цвет c уникальным для столбца V, если цвет c встречается только в этом столбце; аналогично определим цвет, уникальный для строки. Пусть существует столбец, для которого есть не более одного уникального цвета. Тогда выбросим его; в оставшемся прямоугольнике будет встречаться не менее  k – 1 ≥ m + n – 1 цвета, значит, по предположению индукции в нём найдётся нужная четвёрка клеток.
  Осталось разобрать случай, когда в каждом столбце и в каждой строке хотя бы по два уникальных цвета. Рассмотрим любой столбец V₁; пусть в нём два уникальных цвета p и q, и какие-то клетки этих цветов стоят в строках H₁ и H₂ соответственно. В H₁ есть два уникальных цвета; один из них отличен от p. Пусть этот цвет – r, и в H₁ клетка этого цвета стоит в столбце  V₂ ≠ V₁.  Тогда построенные два столбца и две строки – требуемые. Действительно, на их пересечении в V₁ стоят два разных цвета, уникальных для V₁; значит, они не встречаются в V₂. Цвет  r ≠ p  уникален для H₁, значит, он не встречается в H₂. Итого, в нашем пересечении есть различные цвета p, q, r, а также клетка цвета, отличного от них.

Ответ

k = 2n.

Источники и прецеденты использования