Здравствуй, хабрачитатель.
С недавних пор мне нравится проводить конкурсы для программистов-математиков, но эти конкурсы несколько отличаются от олимпиад по программированию, хотя бы тем, что я предлагаю задачи, не имеющие эффективного алгоритма решения. Кроме того, предлагаются задачи, которые либо вообще никто раньше не решал, либо решали очень мало, но серьёзных успехов не добились. Последняя особенность этих задач в том, что они так или иначе связаны с перечислительной комбинаторикой, той областью математики, которая в России была похоронена вместе с другими полезными областями науки «сами знаете когда». Но это менее важно.
Примером такого конкурса является конкурс по задаче о расстановке 6 ферзей на шахматной доске размером n×n. Впервые она была решена именно в рамках моего конкурса (была получена явная формула числа всех конфигураций) и вызвала резонанс в среде тех исследователей, которые занимаются задачами перечислительной комбинаторики. Сама формула позволила исследователям этой задачи строить новые и более сильные гипотезы. Подробнее свою позицию по отношению к такого рода задачам я выражал на Хабре в этой статье.
Другой конкурс, связанный с физикой полимеров, в будущем позволит показать исследователям в этой области, что решётки с дефектами тоже вполне поддаются обсчёту, как и решётки без дефектов, практически нереальные в реальном мире. Это было показано на примере расчёта «предгамильтоновых» циклов. Соответствующий конкурс был подкреплён статьёй про метод динамического программирования. Алгоритм, описанный в этой статье (при соответствующей реализации) на сегодняшний день является самым быстрым в мире (скромно, но так и есть). При более серьезной вычислительной мощности можно было бы говорить о получении существенных результатов в перечислительной комбинаторике… но мечтать не вредно. Короче говоря, этот конкурс тоже оказался полезным для науки.
Теперь я провожу один конкурс «просто так», даже без призового фонда, и предлагаю решить не самые сложные задачи из моего репертуара. Зачем? Просто чтобы любители посоревноваться (разумеется, при наличии свободного времени) могли сразиться с другими такими же любителями. Предлагаемые задачи являются трудными (во всяком случае, не доказано существование эффективного алгоритма их решения), поэтому сражаться придётся не в классическом смысле (как на олимпиаде по программированию – на скорость и качество), а в смысле «у кого подход лучше». А у кого-то может мощности под рукой больше, тоже добро пожаловать. В любом случае, лично меня интересует не кто победит, а сам результат, полученный общими силами в процессе соревнования. Практика показала, что два последних моих конкурса оказались практически полезными для науки.
Сам конкурс будет проходить на моём блоге, на котором помимо других конкурсов опубликованы посты с совершено отличным от программирования смыслом. Вы просто можете не обращать на них внимания, а сразу выбрать в меню раздел «Конкурсы». Дело в том, что создать отдельный ресурс для конкурсов я пока не могу по личным причинам и по причинам недостаточного опыта их проведения, поэтому пока будут тренироваться проведением их на блоге.
Подробное описание задач приводится на страницах конкурса, здесь я кратко обозначу условия.
Задано натуральное число n. Найти такое минимальное натуральное k, что число 3k содержит не менее n подряд идущих нулей в десятичной записи. Например, для n=1 ответом будет k=10, так как 310=59049 и это первая из степеней тройки, которая содержит один ноль. Для n=2 ответом будет k=35, так как 335=50031545098999707 и это первое из степеней тройки, содержащих два нуля.
Есть известная задача о покрытии домино (ссылка на англ.), или задача о димерах. Смысл задачи в том, чтобы посчитать число способов замостить шахматную доску размером m×n доминошками размером 1×2, причём так, чтобы костяшки домино не накладывались друг на друга, не вылезали за края доски и полностью покрывали доску. Например, если n=m=2, то существует всего два способа (обе доминошки вертикально или обе горизонтально).
Теперь давайте «свернём» нашу доску в цилиндр, соединив левую и правую границы. В этом случае любое покрытие можно представить следующим образом: если доминошка вылезает за левый край, то вторая её половинка появляется справа, и наоборот. Требуется посчитать число замощений такого квадратного шахматного цилиндра размером 2n×2n. Для n=1 ответ будет 5, а для n=2, ответ 121… Если не очень ясно, картинки есть на странице конкурса.
Задана квадратная решётка размером n×n. В ней можно обнаружить простые циклы длиной 4, 6, 8, и т. д. до самой большой возможной длины. [ Простой цикл – это цикл, который не имеет самопересечений ]. Например, на решётке размером 2×2 есть один цикл длиной 4. На решётке размером 3×3 есть 4 цикла длиной 4, 4 цикла длиной 6 и 5 циклов длиной 8, то есть ответом будет последовательность [4,4,5]. На решётке 4×4 ответом будет последовательность [9,12,26,52,76,32,6] (длины от 4 до 16). Требуется назвать ответы для n=5,6,…
Итак, добро пожаловать всем участникам. Тех, кто не понимает смысл моих конкурсов и недоброжелателей прошу никак себя не проявлять. Удачи!
PS. Да, было бы уместно опубликовать в блоге «Я пиарюсь», но мне не хватает для этого кармы. К «Спортивному программированию» этот пост тоже имеет отношение.
С недавних пор мне нравится проводить конкурсы для программистов-математиков, но эти конкурсы несколько отличаются от олимпиад по программированию, хотя бы тем, что я предлагаю задачи, не имеющие эффективного алгоритма решения. Кроме того, предлагаются задачи, которые либо вообще никто раньше не решал, либо решали очень мало, но серьёзных успехов не добились. Последняя особенность этих задач в том, что они так или иначе связаны с перечислительной комбинаторикой, той областью математики, которая в России была похоронена вместе с другими полезными областями науки «сами знаете когда». Но это менее важно.
Примером такого конкурса является конкурс по задаче о расстановке 6 ферзей на шахматной доске размером n×n. Впервые она была решена именно в рамках моего конкурса (была получена явная формула числа всех конфигураций) и вызвала резонанс в среде тех исследователей, которые занимаются задачами перечислительной комбинаторики. Сама формула позволила исследователям этой задачи строить новые и более сильные гипотезы. Подробнее свою позицию по отношению к такого рода задачам я выражал на Хабре в этой статье.
Другой конкурс, связанный с физикой полимеров, в будущем позволит показать исследователям в этой области, что решётки с дефектами тоже вполне поддаются обсчёту, как и решётки без дефектов, практически нереальные в реальном мире. Это было показано на примере расчёта «предгамильтоновых» циклов. Соответствующий конкурс был подкреплён статьёй про метод динамического программирования. Алгоритм, описанный в этой статье (при соответствующей реализации) на сегодняшний день является самым быстрым в мире (скромно, но так и есть). При более серьезной вычислительной мощности можно было бы говорить о получении существенных результатов в перечислительной комбинаторике… но мечтать не вредно. Короче говоря, этот конкурс тоже оказался полезным для науки.
Теперь я провожу один конкурс «просто так», даже без призового фонда, и предлагаю решить не самые сложные задачи из моего репертуара. Зачем? Просто чтобы любители посоревноваться (разумеется, при наличии свободного времени) могли сразиться с другими такими же любителями. Предлагаемые задачи являются трудными (во всяком случае, не доказано существование эффективного алгоритма их решения), поэтому сражаться придётся не в классическом смысле (как на олимпиаде по программированию – на скорость и качество), а в смысле «у кого подход лучше». А у кого-то может мощности под рукой больше, тоже добро пожаловать. В любом случае, лично меня интересует не кто победит, а сам результат, полученный общими силами в процессе соревнования. Практика показала, что два последних моих конкурса оказались практически полезными для науки.
Задачи
Сам конкурс будет проходить на моём блоге, на котором помимо других конкурсов опубликованы посты с совершено отличным от программирования смыслом. Вы просто можете не обращать на них внимания, а сразу выбрать в меню раздел «Конкурсы». Дело в том, что создать отдельный ресурс для конкурсов я пока не могу по личным причинам и по причинам недостаточного опыта их проведения, поэтому пока будут тренироваться проведением их на блоге.
Подробное описание задач приводится на страницах конкурса, здесь я кратко обозначу условия.
Задача 1. Три в степени n
Задано натуральное число n. Найти такое минимальное натуральное k, что число 3k содержит не менее n подряд идущих нулей в десятичной записи. Например, для n=1 ответом будет k=10, так как 310=59049 и это первая из степеней тройки, которая содержит один ноль. Для n=2 ответом будет k=35, так как 335=50031545098999707 и это первое из степеней тройки, содержащих два нуля.
Задача 2. Димеры на цилиндре
Есть известная задача о покрытии домино (ссылка на англ.), или задача о димерах. Смысл задачи в том, чтобы посчитать число способов замостить шахматную доску размером m×n доминошками размером 1×2, причём так, чтобы костяшки домино не накладывались друг на друга, не вылезали за края доски и полностью покрывали доску. Например, если n=m=2, то существует всего два способа (обе доминошки вертикально или обе горизонтально).
Теперь давайте «свернём» нашу доску в цилиндр, соединив левую и правую границы. В этом случае любое покрытие можно представить следующим образом: если доминошка вылезает за левый край, то вторая её половинка появляется справа, и наоборот. Требуется посчитать число замощений такого квадратного шахматного цилиндра размером 2n×2n. Для n=1 ответ будет 5, а для n=2, ответ 121… Если не очень ясно, картинки есть на странице конкурса.
Задача 3. Статистика циклов на квадратной решётке
Задана квадратная решётка размером n×n. В ней можно обнаружить простые циклы длиной 4, 6, 8, и т. д. до самой большой возможной длины. [ Простой цикл – это цикл, который не имеет самопересечений ]. Например, на решётке размером 2×2 есть один цикл длиной 4. На решётке размером 3×3 есть 4 цикла длиной 4, 4 цикла длиной 6 и 5 циклов длиной 8, то есть ответом будет последовательность [4,4,5]. На решётке 4×4 ответом будет последовательность [9,12,26,52,76,32,6] (длины от 4 до 16). Требуется назвать ответы для n=5,6,…
Итак, добро пожаловать всем участникам. Тех, кто не понимает смысл моих конкурсов и недоброжелателей прошу никак себя не проявлять. Удачи!
PS. Да, было бы уместно опубликовать в блоге «Я пиарюсь», но мне не хватает для этого кармы. К «Спортивному программированию» этот пост тоже имеет отношение.
