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

В таблице <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 клетки, занумерованные разными числами, что на каждой вертикали и на каждой горизонтали найдётся хотя бы по одной выбранной клетке.