Кожевников П.А. Задача Шаповалова о ладье

Математическое образование, 2000г, № 4

Задача создана в соавторстве с моим учеником Рустамом Садыковым: он этот факт заметил, а я – доказал. Впервые дана на Турнире городов весной 1999 г. Ещё эта задача разобрана в статье "Путь хромой ладьи" (см. ниже).

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

Кноп К.А. Тайна фальшивых монеток

Этот сюжет и набор задач впервые дан на Кубке Колмогорова 2007 г.

Суду предъявлены 29 одинаковых с виду монет, среди которых есть фальшивые. Суд знает, что среди них одна или две фальшивые, все настоящие монеты весят одинаково, фальшивые – тоже одинаково, но легче настоящих. Адвокат знает, какие монеты на самом деле фальшивые, но. Однако ему нужно сообщить суду истинное число фальшивых монет, и для этого можно проводить взвешивания на чашечных весах без гирь. Однако адвокат связан обязательством не разглашать ни про какую монету фальшивая она или настоящая: он не имеет права делать взвешивания, из которой такую информацию можно логически вывести. Может ли адвокат, не нарушая обязательства, убедить суд, что фальшивых монет две, а не одна?

Хованова Т.А. «Колонна мудрецов» (на англ. языке)

Tanya Khovanova "A Line of Sages" - The Mathematical Intelligencer, November 2013

Задача создана в соавторстве с К.А.Кнопом: я придумал постановку и несколько алгоритмов для более 500, но далёких от максимума. К.Кноп помог существенно улучшить результат, подойдя к максимуму почти вплотную. Наконец, я получил максимум.
Задача впервые дана на Турнире городов весной 2013 г.

Для прохождения теста тысячу мудрецов выстраивают в колонну. Из колпаков с номерами от 1 до 1001 один прячут, а остальные в случайном порядке надевают на мудрецов. Каждый видит только номера на колпаках всех впереди стоящих. Далее мудрецы по порядку от заднего к переднему называют вслух целые числа. Каждое число должно быть от 1 до 1001, причем нельзя называть то, что уже было сказано. Результат теста – число мудрецов, назвавших номер своего колпака. Мудрецы заранее знали условия теста и могли договориться, как действовать.
а) Могут ли они гарантировать результат более 500?
б) Могут ли они гарантировать результат не менее 999?

Две фирмы по очереди нанимают программистов, среди которых есть 11 всем известных гениев. Первого программиста каждая фирма выбирает произвольно, а каждый следующий должен быть знаком с кем-то из ранее нанятых данной фирмой. Если фирма не может нанять программиста по этим правилам, она прекращает прием, а другая может продолжать. Список программистов и их знакомств заранее известен. Могут ли знакомства быть устроены так, что фирма, вступающая в игру второй, сможет нанять 10 гениев, как бы ни действовала первая фирма?

Медников Л.Э. "Путь хромой ладьи"

Империя математики, 2000г, № 1

Задача справа создана в соавторстве с моим сыном Максимом. Впервые дана на Турнире городов весной 2001 г. А всего в статье разобраны 3 моих задачи.

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

А.Шаповалов, А.Лебедев "Задача о самопересекающейся ломаной"

Квант, 2014г, № 1

Задача впервые дана на Турнире городов осенью 2013 г.

На плоскости нарисована замкнутая самопересекающаяся ломаная. Она пересекает каждое свое звено ровно один раз, причём через каждую точку самопересечения проходят ровно два звена. Может ли каждая точка самопересечения делить оба этих звена пополам? (Нет самопересечений в вершинах и звеньев с общим отрезком.)

Обсуждение на dxdy.ru

Задача впервые дана на Турнире городов весной 2009 г.

Натуральное число увеличили на 10% и снова получили натуральное число.
Могла ли при этом сумма цифр уменьшиться ровно на 10%?

К. Кноп "Испытание для трубадура"

Задача (а) справа создана в соавторстве с В.Шориным. Впервые дана на Турнире им. Савина в 1999 г. Задача (б) создана в соавторстве с А.Спиваком, была на Московской олимпиаде 2000 г. Интересный исторический обзор о предшественниках и последователях можно найти в послесловии К.Кнопа к задаче о трубадуре.

Н.Белухов, Э.Колев "Поиск движущейся цели в графе"(на англ. языке)

Nikolai Beluhov, Emil Kolev "Search for a moving target in a graph" - Fifteenth International Workshop on Algebraic and Combinatorial Coding Theory June 18-24, 2016, Albena, Bulgaria pp. 47-52

а) В одном из 1000 окопов, расположенных в ряд, спрятался робот-пехотинец. Автоматическая пушка может одним выстрелом накрыть любой окоп. В каждом промежутке между выстрелами робот (если уцелел) обязательно перебегает в соседний окоп (быть может, только что обстрелянный). Сможет ли пушка наверняка накрыть робота?
б) Система укреплений состоит из блиндажей. Некоторые из блиндажей связаны траншеями, причем из любого блиндажа можно перебежать в какой-нибудь другой. В одном из блиндажей спрятался пехотинец. Пушка может одним выстрелом накрыть любой блиндаж. В каждом промежутке между выстрелами пехотинец обязательно перебегает по одной из траншей в соседний блиндаж (даже если по соседнему блиндажу только что стреляла пушка, пехотинец может туда перебежать). Назовем систему надежной, если у пушки нет гарантированной стратегии поражения пехотинца (то есть такой последовательности выстрелов, благодаря которой пушка поразит пехотинца независимо от его начального положения и последующих передвижений).
б1) Докажите, что система укреплений, изображенная на рисунке, надежна.
б2)) Найдите все такие надежные системы, которые перестают быть надежными при выкидывании любой траншеи.

К. М. Свансон, Д. Р. Стинсон «Комбинаторные решения, обеспечивающие повышенную безопасность для обобщенной Русской карточной задачи» (на англ. языке)

Colleen M. Swanson, Douglas R. Stinson "Combinatorial solutions providing improved security for the generalized Russian cards problem " - Des. Codes Cryptogr. (2014) 72:345–367

Судя по обширной библиографии к статье, обобщенная задача создала целое направление в криптографии.
Задача впервые дана на Московской математической олимпиаде 2000 г.
В июне 2017 г. на сайте Problems.ru опубликовано замечательное решение К.Кнопа через конечную проективную плоскость.

Из колоды вынули семь карт, показали всем, перетасовали и раздали Грише и Лёше по три карты, а оставшуюся карту
а) спрятали;
б) отдали Коле.
Гриша и Лёша могут по очереди сообщать вслух любую информацию о своих картах. Могут ли они сообщить друг другу свои карты так, чтобы при этом Коля не смог вычислить местонахождение ни одной из тех карт, которых он не видит? (Гриша и Лёша не договаривались о каком-либо особом способе общения; все переговоры происходят открытым текстом.)
Problems.ru#105089

Николай Белухов «Змеиные пути в графах короля и коня» (на англ. языке)

Nikolai Beluhov "Snake Paths in King and Knight Graphs" - arXiv:2301.01152v3

Задача справа создана в соавторстве с моим сыном Максимом. Впервые дана на Кубке Колмогорова 2008 г., тур 2

Вася отметил на доске 100х100 несколько клеток и разрешил королю ходить только по отмеченным клеткам. Затем Вася выбрал 2 отмеченные клетки и сообщил Пете минимальное число ходов короля от одной до другой. Какое наибольшее число мог услышать Петя?