![]() ![]()
Пожалуйста, не пишите нам, что вы не можете решить задачу.
Если вы не можете ее решить, значит вы не можете ее решить :-)
Задачу решили:
2
всего попыток:
3
Английский математик Джон Хортон Конвей изобрел множество математических развлечений, доставляющих не только удовольствие, но и пищу для серьезных размышлений. Одно из его изобретений – язык программирования FRACTRAN, о котором пойдет речь в данной задаче.
Память данных виртуальной машины языка FRACTRAN содержит одно единственное целое число, а программа представляет собой упорядоченную последовательность рациональных дробей. На каждом шаге выполнения программы машина просматривает эти дроби одну за другой слева направо и умножает каждую из них на число из памяти, пока произведение не окажется целым. Полученное целое число записывают в память вместо предыдущего. Вот, например, FRACTRAN-программа, предложенная Конвеем для получения последовательности простых чисел: 17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1. Записав в память исходное значение 2, получим в памяти ряд чисел в следующей последовательности: 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30, ..., 136, 8, 60, ..., 544, 32, 240, ... Оказывается, степени двойки в полученной последовательности встречаются только с простыми показателями: 22, 23, 25, ..., и можно проверить, что данная последовательность будет содержать в порядке возрастания все степени двух с простыми показателями. Заметим, что для получения 22 из исходного числа 2 потребовалось 19 шагов программы, и при этом три раза происходило умножение на дробь 13/11. А сколько раз придется выполнить умножение на 13/11 при переходе от исходного числа 2 к 2111119?
![]()
Задачу решили:
4
всего попыток:
4
Рассмотрим игру на прямоугольной клетчатой доске. Одна клетка доски не занята, на остальных стоят фишки. Каждым ходом игрок передвигает на свободную клетку одну из соседних (по вертикали или горизонтали) фишек. В начале игры пустая клетка находится в правом нижнем углу, в левом верхнем углу находится красная фишка, а на остальных клетках стоят синие фишки. Цель игры — переместить красную фишку в правый нижний угол за наименьшее количество ходов. На рисунке ниже показана последовательность ходов для доски 2 х 2. Пусть S(m,n) -минимальное количество ходов, необходимое для перемещения красной фишки в правый нижний угол для доски m х n. Можно проверить, что S(5,4) = 25. Существует всего 256 различных досок с сторонами m и n, не превышающими 100, для которых S(m,n) является квадратом натурального числа. Подсчитайте количество досок со сторонами m и n, не превышающими 1010, для которых S(m,n) является квадратом натурального числа. ![]()
Задачу решили:
14
всего попыток:
29
Сэм и Макс решили сделать из электронных часов прибор для демонстрации последовательности математических вычислений. Для испытания они запрограммировали его на расчет однозначной суммы цифр натуральных чисел. Напомним, что для вычисления однозначной суммы цифр суммируют все десятичные цифры числа, затем все десятичные цифры результата, и так далее, пока не получится однозначное число. Когда в прибор передают очередное число, оно отображается индикатором, затем отображаются все промежуточные значения, и, наконец, - результат. Например, если взять число 137, индикатор покажет последовательность "137"→"11"→"2", а затем погаснет до прихода нового числа. Каждая цифра на индикаторе состоит из нескольких отрезков, как показано на рисунке. Например, цифра "8" использует семь отрезков – четыре вертикальных и три горизонтальных, цифра "1" состоит из двух вертикальных, а именно, правого верхнего и правого нижнего, а цифра "4" – из четырех отрезков: левого верхнего, правого верхнего и правого нижнего вертикальных и горизонтального, лежащего посередине. Индикатор потребляет электроэнергию, только когда отрезки включаются или выключаются. Так, включение или выключение числа 2 требует пяти единиц энергии, а числа 7 – четырех единиц энергии. Сэм и Макс предложили разные конструкции прибора. Работа прибора Сэма показана на картинке слева. Когда этот прибор получает число 137, оно отображается на индикаторе, затем полностью гаснет, затем прибор показывает число 11, которое также гаснет, и, наконец, загорается число 2, которое тоже гаснет В таблице приведен расчет энергопотребления прибора Сэма для числа 137. "137":(2 + 5 + 4) ?× 2 = 22 переключений ("137" включается и выключается). "11":(2 + 2) × 2 = 8 переключений ("11" включается и выключается). "2":(5) × 2 = 10 переключений ("2" включается и выключается). Всего получается 40 переключений и, соответственно, тратится 40 единиц энергии. Прибор Макса (изображен справа) работает по-другому. Он не выключает каждый раз весь индикатор, а выбирает только те отрезки, которые не понадобятся для следующего числа. Вот, как он будет работать с числом 137: "137":2 + 5 + 4 = 11 переключений (включение трех цифр числа "137"), 7 переключений (выключение отрезков, не нужных для числа "11"). 0 переключений (число "11" уже и так горит) "11":3 переключения (выключение первой единички и нижней части второй единички; верхняя часть остается гореть, поскольку она нужна для цифры "2"). "2":4 переключения (включение оставшихся отрезков цифры "2"), 5 переключений (выключение цифры "2"). Итого: 30 переключений. Понятно, что прибор Макса тратит меньше энергии. Так, при подсчете однозначной суммы цифр для числа 137 экономия составляет 10 единиц энергии. Найдите общую экономию энергии при подсчете однозначной суммы цифр для всех простых чисел, не превышающих 2×107. ![]()
Задачу решили:
4
всего попыток:
15
Рассмотрим последовательность y0, y1, y2,..., где yi - 32-битные случайные целые числа, т.е. 0≤yi<232, и все значения y равновероятны. Последовательность xi задается рекурсивно следующим образом:
Ясно, что в конце концов появится такой индекс N для которого xi окажется равным 232-1 при всех i≥N. Найдите математическое ожидание величины N2. Результат умножьте на миллион и округлите вниз до целого. ![]()
Задачу решили:
1
всего попыток:
1
Обозначим через f(n) количество способов, которыми можно построить башню 3×3×n из блоков 2×1×1. Блоки можно вращать произвольным образом. При этом башни, отличающиеся поворотом или симметрией, считаются различными. Например, f(2) = 229, f(4) = 117805, f(6) = 64647289, f(63) mod 123456789 = 75292539, f(66) mod 123456789 = 56150940. Здесь a mod q означает остаток от деления a на q. Найдите f(612345) mod 123456789. ![]()
Задачу решили:
1
всего попыток:
2
В этой задаче рассматривается еще одна игра, похожая на ним, где два игрока по очереди берут камни из двух куч. Каждым ходом игрок берет камни из одной кучи в количестве, кратном количеству камней в другой куче. Как обычно, проигрывает тот, кто не может сделать очередной ход, т. е. когда в одной из куч камней не осталось. Опишем начальную позицию в виде упорядоченной пары чисел. Например, пара (6, 14) соответствует положению, при котором в меньшей куче 6 камней, а в большей — 14. В этом случае первый игрок может взять из большей кучи 6 или 12 камней. Выигрышной называется позиция, которая позволяет первому игроку выиграть при верном выборе стратегии. Остальные позиции называются проигрышными. Например, позиции (1,5), (2,6) и (3,12) — выигрышные, поскольку первый игрок может первым же ходом забрать все камни из второй кучи. Позиции (2,3) и (3,4) — проигрышные, поскольку при любом ходе первого игрока второй участник получает выигрышную позицию. Обозначим через Z(N) сумму (yi-xi) для всех проигрышных позиций (xi,yi), 0 < xi< yi ≤ N. Можно проверить, что Z(10) = 27 и Z(104) = 24319983959. Найдите остаток от деления Z(1016) на 710. ![]()
Задачу решили:
1
всего попыток:
1
Рассмотрим пару последовательностей an и s n , заданных следующим образом: a1 = 1, s1 = 1, an = sn-1 mod n, sn = sn-1+ an×n. (Здесь и далее "x mod y" означает остаток от деления x на y.) Первые 10 элементов последовательности an: 1,1,0,3,0,3,5,4,1,9. Первые 10 элементов последовательности sn: 1,3,3,15,15,33,68,100,109,199. Обозначим через h(N,M) количество таких пар (p,q), для которых 1≤p≤q≤N и (sp + sp+1 +… + sq-1 + sq ) mod M = 0 Можно проверить, что h(10,10)=5, а соответствующие пары – (1,6), (4,5), (4,9), (6,9) и (8,8). h(104,103)= 107796. Найдите h(1012,106). ![]()
Задачу решили:
1
всего попыток:
4
Широко известна игра, где один из участников задумывает целое число, а другой пытается его угадать, задавая вопросы. В этой задаче исследуется вариант такой игры, когда задумывают натуральное число из промежутка [1,n], а в качестве вопросов разрешается называть натуральные числа из этого же интервала. При этом стоимость каждого вопроса равна названному числу. Допускаются ответы трех видов:
Требуется определить задуманное число и при этом минимизировать суммарную стоимость вопросов (в дальнейшем – цена игры). Для данного числа n назовем стратегию оптимальной, если она минимизирует цену игры для самого неудачного задуманного числа. Например, при n=3 наилучшим первым ходом будет число "2". После этого при любом ответе можно будет точно определить задуманное число, поэтому больше вопросов не потребуется, и цена игры будет равна 2. Если n=8, мы могли бы выбрать в качестве стратегии "бинарный поиск". Если первым ходом мы назовем число "4", а задуманное число будет больше, чем 4, нам потребуется еще два вопроса. Пусть вторым ходом мы называем число "6". Если задуманное число больше, чем 6, нам потребуется еще один ход, скажем, "7", и цена игры составит 4+6+7=17. Мы можем существенно улучшить нашу стратегию для n=8, если первым ходом назовем число "5". Если задуманное число больше, чем 5, то вторым ходом мы можем назвать число "7", и этого будет достаточно для нахождения задуманного. Тогда цена игры составит 5+7=12. Если же задуманное число меньше, чем 5, то для его определения достаточно вторым и третьим ходом назвать "3" и "1", а цена игры составит 5+3+1=9. Поскольку 12 > 9, в худшем случае цена игры при этой стратегии будет равна 12. Получается, что данная стратегия более выгодна, чем предыдущая, и оказывается, что она оптимальна, то есть никакая другая стратегия не может гарантировать для n=8 результат меньший, чем 12. Пусть C(n) – максимальная цена игры, которая может получиться для оптимальной стратегии в худшем случае. Тогда C(1) = 0, C(2) = 1, C(3) = 2 и C(8) = 12. Можно подсчитать, что C(100) = 400. Найдите С(500000).
Внимание! Если Вы увидите ошибку на нашем сайте, выделите её и нажмите Ctrl+Enter.
|