Олимпиадные задачи по теме «Комбинаторика» для 9 класса - сложность 3-4 с решениями

В таблице <i>m</i> строк, <i>n</i> столбцов. <i>Горизонтальным ходом</i> называется такая перестановка элементов таблицы, при которой каждый элемент остаётся в той строке, в которой он был и до перестановки; аналогично определяется <i>вертикальный ход</i> ("строка" в предыдущем определении заменяется на "столбец"). Укажите такое <i>k</i>, что за <i>k</i> ходов (любых) можно получить любую перестановку элементов таблицы, но существует такая перестановка, которую нельзя получить за меньшее число ходов.

Числа 1, 2, 3, ..., <i>N</i> записываются в строчку в таком порядке, что если где-то (не на первом месте) записано число <i>i</i>, то где-то слева от него встретится хотя бы одно из чисел  <i>i</i> + 1  и  <i>i</i> – 1.  Сколькими способами это можно сделать?

Клетки шахматной доски 8×8 как-то занумерованы числами от 1 до 32, причём каждое число использовано дважды. Докажите, что можно так выбрать 32 клетки, занумерованные разными числами, что на каждой вертикали и на каждой горизонтали найдётся хотя бы по одной выбранной клетке.

<i>N</i> друзей одновременно узнали <i>N</i> новостей, причём каждый узнал одну новость. Они стали звонить друг другу и обмениваться новостями.

Каждый разговор длится 1 час. За один разговор можно передать сколько угодно новостей.

Какое минимальное количество часов необходимо, чтобы все узнали все новости? Рассмотрите три случая:

  а)  <i>N</i> = 64,

  б)  <i>N</i> = 55,

  в)  <i>N</i> = 100.

В таблице <i>N</i>×<i>N</i>, заполненной числами, все строки различны (две строки называются различными, если они отличаются хотя бы в одном элементе).

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