В клетках квадратной таблицы $n\times n$, где  $n$ > 1,  требуется расставить различные целые числа от 1 до $n^2$ так, чтобы каждые два последовательных числа оказались в соседних по стороне клетках, а каждые два числа, дающие одинаковые остатки при делении на $n$, – в разных строках и в разных столбцах. При каких $n$ это возможно?

   Решение

Темы:    [ Комбинаторика (прочее) ] [ Принцип крайнего ] [ Мощность множества. Взаимно-однозначные отображения ] [ Упорядочивание по возрастанию (убыванию) ] [ Оценка + пример ]

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

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

Условие

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

Подсказка

Рассмотрите либо четыре самых больших, либо четыре самых меньших числа.

Решение

  Пример множества из 7 элементов:  {–3, –2, –1, 0, 1, 2, 3}.
  Докажем, что множество  M = {a₁, a₁, ..., a_n}  из  n > 7  чисел требуемым свойством не обладает. Можно считать, что   a₁ > a₂ > a₃ > ... > a_n   и  a₄ > 0  (смена знаков всех элементов наше свойство не меняет). Тогда   a₁ + a₂ > a₁ + a₃ > a₁ + a₄ > a₁,   то есть ни одна из сумм  a₁ + a₂,  a₁ + a₃  и  a₁ + a₄  множеству M не принадлежит. Кроме того, суммы  a₂ + a₃  и  a₂ + a₄  не могут одновременно принадлежать M, поскольку  a₂ + a₃ > a₂ + a₄ > a₂.  Получается, что по крайней мере для одной из троек  (a₁, a₂, a₃)  и  (a₁, a₂, a₄)  сумма любых двух её элементов множеству M не принадлежит.

Ответ

7 элементов.

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