2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Конкурс для программистов - 3^n, димеры и статистика циклов
Сообщение21.11.2010, 21:11 


26/01/10
959
Модераторам: форум dxdy указан на странице конкурса в качестве информационного спонсора.

Предлагаю принять участие в моём новом конкурсе для программистов-математиков. На этот раз никакого призового фонда не будет, зато задачи попроще и моего участия не предвидится.

Подробные условия задач на странице конкурса. Здесь лишь кратко обозначу постановку задач.

Задача 1. $3^n$.

Задано натуральное число $n$, требуется отыскать такое минимальное натуральное число $k$, что $3^k$ содержит не менее $n$ подряд идущих нулей. Например, для $n=1$ ответ $k=10$, а для $n=2$ ответ $k=35$.

В энциклопедии уже есть ответы для аналогичной задачи, но для $2^n$ (A006889), а для $3^n$ есть только поиск подряд идущих девяток (A131544), восьмёрок, семёрок, ..., а нулей нет! Торопитесь исправить это недоразумение.

Задача 2. Димеры на цилиндре.

Вспомним классическую задачу про "паркет" (изначально - это задача о димерах). Задана прямоугольная шахматная доска размером $n\times n$. Сколькими способами можно замостить доску костяшками домино размером $1\times 2$? Костяшки не могут выходить за края доски, накладываться друг на друга. Вся доска должна быть замощена. Например, для $m=n=2$ ответ 2, то есть всего два способа.

Теперь усложняем условие: сворачиваем доску в цилиндр, соединяя левую и правую границы. В этом случае, если костяшка "вылезает" за левую границу, то её половинка появляется справа, и наоборот. Сколько существует замощений квадратного шахматного цилиндра размером $2n\times 2n$? Если $n=1$ (цилиндр $2\times 2$), то ответ 5. Если $n=2$, то ответ 121.

Задача 3. Статистика циклов на решётке.

Задана решётка размером $n\times n$. В ней можно обнаружить простые циклы (без самопересечений) длиной 4, 6, 8, и т. д. Требуется для заданного натурального $n>1$ сказать, сколько на решётке $n\times n$ простых циклов всех возможных чётных длин (нечётных там нет). Например, для $n=1$ ответом будет один цикл длиной 4. Для $n=2$ имеем циклы длиной 4, 6 и 8 в количестве 4, 4 и 5 соответственно. Для $n=3$ ответом будет последовательность [9,12,26,52,76,32,6]. (9 циклов длиной 4, 12 циклов длиной 6, ..., 6 циклов длиной 16).

Удачи!

 Профиль  
                  
 
 Re: Конкурс для программистов - 3^n, димеры и статистика циклов
Сообщение09.12.2010, 08:09 


26/01/10
959
Конкурс завершён. Можно ознакомиться с итогами.
Всем спасибо за явное и неявное участие.

 Профиль  
                  
 
 Posted automatically
Сообщение04.11.2013, 01:55 
Основатель
Аватара пользователя


11/05/05
4313
 i  Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group