Олимпиадные задачи по теме «Системы счисления» - сложность 4 с решениями
Системы счисления
НазадНазовём тройку чисел<i>триплетом</i>, если одно из них равно среднему арифметическому двух других. Последовательность $(a_n)$ строится следующим образом: $a_0 = 0$, $a_1 = 1$ и при $n > 1$ число $a_n$ — такое минимальное натуральное число, большее $a_{n-1}$, что среди чисел $a_0$, $a_1$, ..., $a_n$ нет трёх, образующих триплет. Докажите, что $a_{2023} \leqslant 100,000$.
Король решил поощрить группу из $n$ мудрецов. Их поставят в ряд друг за другом (чтобы все смотрели в одном направлении), на каждого наденут чёрную или белую шляпу. Каждый будет видеть шляпы всех впереди стоящих. Мудрецы по очереди (от последнего к первому) назовут цвет (белый или чёрный) и натуральное число по своему выбору. В конце подсчитывается число мудрецов, которые назвали цвет, совпадающий с цветом своей шляпы: ровно столько дней всей группе будут платить надбавку к жалованью. Мудрецам разрешили договориться заранее, как отвечать. При этом мудрецы знают, что ровно $k$ из них безумны (кто именно – им неизвестно). Безумный мудрец называет белый или чёрный цвет и число вне зависимости от договорённостей. Какое максимальное число дней с надбавкой к жалованью могут гарантировать группе м...
Дано иррациональное число α, 0 < α < ½. По нему определяется новое число α<sub>1</sub> как меньшее из двух чисел 2α и 1 – 2α. По этому числу аналогично определяется α<sub>2</sub>, и так далее.
а) Докажите, что α<sub><i>n</i></sub> < <sup>3</sup>/<sub>16</sub> для некоторого <i>n</i> .
б) Может ли случиться, что α<sub><i>n</i></sub> > <sup>7</sup>/<sub>40</sub> при всех натуральных <i>n</i>?
Обозначим через <i>S</i>(<i>k</i>) сумму цифр натурального числа <i>k</i>. Натуральное число <i>a</i> назовём <i>n-хорошим</i>, если существует такая последовательность натуральных чисел <i>a</i><sub>0</sub>, <i>a</i><sub>1</sub>, ..., <i>a<sub>n</sub></i>, что <i>a<sub>n</sub> = a</i> и <i>a</i><sub><i>i</i>+1</sub> = <i>a<sub>i</sub> – S</i>(<i>a<sub>i</sub></i>) при всех <i>i</i> = 0, 1, ..., <i>n</i> – 1. Верно ли, что для любого натурального <i>n</i> существует натуральное число, являющееся <i>n<...
Докажите, что для любого натурального <i>n</i> найдётся натуральное число, десятичная запись квадрата которого начинается <i>n</i> единицами, а заканчивается какой-то комбинацией из <i>n</i> единиц и двоек.
<b>Игра ``Шоколадка''.</b>Имеется шоколадка, состоящая из6×8 = 48 долек. Одна из долек отмечена:<div align="CENTER">
$x$
</div>Двое игроков по очереди разламывают ее по какой-нибудь прямой, делящей шоколадку на дольки, и съедают ту половину, которая не содержит отмеченной дольки. Проигрывает тот, кто не может сделать хода, то есть ему остается лишь одна отмеченная долька. а) Опишите выигрышную стратегию в этой игре. Кто из игроков выиграет при данных начальных условиях? б) При каких размерах шоколадки начинающий игрок выигрывает при любом расположении отмеченной дольки? в) При каких размерах шоколадки начинающий игрок проигрывает при любом расположении отмеченной дольки?
<b>Последовательность Морса.</b>Бесконечная последовательность из нулей и единиц<div align="CENTER"> 0110 1001 1001 0110 1001... </div>построена по следующему правилу. Сначала написан нуль. Затем делается бесконечное количество шагов. На каждом шаге к уже написанному куску последовательности приписывается новый кусок той же длины, получаемый из него заменой всех нулей единицами, а единиц — нулями. а) Какая цифра стоит на 2001 месте? б) Будет ли эта последовательность, начиная с некоторого места, периодической? в) Докажите, что данная последовательность переходит в себя при замене каждого нуля на комбинацию 01, а каждой единицы — на комбинацию 10. г) Докажите, что ни одно конечно слово из нулей и единиц не встречается в последовательности Морса три раза под...
Определим последовательности чисел (<i>x<sub>n</sub></i>) и (<i>d<sub>n</sub></i>) условиями <i>x</i><sub>1</sub> = 1, <i>x</i><sub><i>n</i>+1</sub> = [ <img width="103" height="39" align="MIDDLE" border="0" src="/storage/problem-media/60875/problem_60875_img_2.gif"> ], <i>d<sub>n</sub></i> = <i>x</i><sub>2<i>n</i>+1</sub> – 2<i>x</i><sub>2<i>n</i>–1</sub> (<i>n</i> ≥ 1).
Докажите, что число <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-me...
Какое наименьшее число гирь необходимо для того, чтобы иметь возможность взвесить любое число граммов от 1 до 100 на чашечных весах, если гири можно класть на обе чашки весов?