Олимпиадные задачи из источника «глава 5. Числа, дроби, системы счисления» - сложность 2-3 с решениями

Найти все такие натуральные <i>n</i>, для которых числа ¹/_<i>n</i> и ¹/_<i>n</i>+1 выражаются конечными десятичными дробями.

Упростите выражение (избавьтесь от как можно большего количества знаков корней):   <img align="absmiddle" src="/storage/problem-media/64993/problem_64993_img_2.gif"> .

<b>4 монеты.</b>Из четырех монет одна фальшивая (она отличается по весу от настоящей, но не известно, в какую сторону). Требуется за два взвешивания на двухчашечных весах без гирь найти фальшивую монету.

Проанализируйте при помощи ним-сумм игру ``Йога''из задачи <a href="https://mirolimp.ru/tasks/160647">4.21</a>.

<b>Марсианские амебы II.</b>При помощи ним-сумм (смотри задачу<a href="https://mirolimp.ru/tasks/160914">5.76</a>) можно исследовать самые разные игры и процессы. Например, можно получить еще одно решение задачи <a href="https://mirolimp.ru/tasks/160646">4.20</a>. Постройте на множестве марсианских амеб{<i>A</i>, <i>B</i>, <i>C</i>} функцию<i>f</i>, для которой выполнялись бы равенства<div align="CENTER"> <i>f</i> (<i>A</i>) $\displaystyle \oplus$ <i>f</i> (<i>B</i>) = <i>f</i> (<i>C</i>),    <i>f</i> (<i>A</i>) $\displaystyle \oplus$ <i>f</i> (<i>C</i>)...

<b>Игра ``Ним''.</b>Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять любое (ненулевое) количество камней, но только из одной кучки. Выигрывает тот, кто взял последний камень. Для анализа игры каждому набору кучек камней<i>m</i>₁,<i>m</i>₂, ...,<i>m</i>_lпоставим в соответствие его ним сумму (<a href="https://mirolimp.ru/tasks/160914">5.1</a>). а) Докажите, что если игрок делает ход из позиции с нулевой ним-суммой, то в результате получается позиция с ним-суммой<i>n</i>$\ne$0. б) Докажите, что из позиции с ненулевой ним-суммой всегда можно сделать ход в позицию с ним-суммой<i>n&...

<b>Ним-сумма.</b>Будем говорить, что число<i>n</i>является ним-суммой чисел<i>m</i>и<i>k</i>(<i>m</i>$\oplus$<i>k</i>=<i>n</i>), если оно получается из чисел<i>m</i>и<i>k</i>после следующих преобразований. 1)<i>m</i>и<i>k</i>записываются в двоичной системе счисления<div align="CENTER"> <i>m</i> = (<i>m</i>_s...<i>m</i>₁<i>m</i>₀)₂,        <i>k</i> = (<i>k</i>_s...<i>k</i>₁<i>k</i>₀)<sub>2...

<b>Задача Иосифа Флавия.</b><i>n</i>человек выстраиваются по кругу и нумеруются числами от 1 до<i>n</i>. Затем из них исключается каждый второй до тех пор, пока не останется только один человек. Например, если<i>n</i>= 10, то порядок исключения таков: 2, 4, 6, 8, 10, 3, 7, 1, 9, так что остается номер 5. Для данного<i>n</i>будем обозначать через<i>J</i>(<i>n</i>) номер последнего оставшегося человека. Докажите, что а)<i>J</i>(2<i>n</i>) = 2<i>J</i>(<i>n</i>) - 1; б)<i>J</i>(2<i>n</i>+ 1) = 2<i>J</i>(<i>n</i>) + 1; в) если<i>n</i>= (1<i>b</i>_{m - 1}<i>b</i>&...

<b>Ханойская башня и двоичная система счисления.</b>Рассмотрим два процесса, каждый из которых состоит из 2⁸- 1 шагов. Первый — это процесс решения головоломки ``Ханойская башня'' (смотри задачу<a href="https://mirolimp.ru/tasks/160315">1.42</a>) при помощи оптимального алгоритма. Второй — это процесс прибавления единицы, который начинается с 0 и заканчивается числом 2⁸- 1. Опишите связь между этими двумя процессами.

<b>Множество Кантора.</b>Отрезок числовой оси от 0 до 1 покрашен в зеленый цвет. Затем его средняя часть — интервал (1/3;2/3) перекрашивается в красный цвет, потом средняя часть каждого из оставшихся зелеными отрезков тоже перекрашивается в красный цвет, с оставшимися зелеными отрезками проделывается та же операция и так до бесконечности. Точки, оставшиеся зелеными, образуют множество Кантора. а) Найдите сумму длин красных интервалов. б) Докажите, что число 1/4 останется окрашенным в зеленый цвет. в) Из суммы<div align="CENTER"> $\displaystyle {\textstyle\dfrac{2}{3}}$ + $\displaystyle {\textstyle\dfrac{2}{9}}$ + $\displaystyle {\textstyle\dfrac{2}{27}}$ + $\displaystyle {\textstyle\dfrac{2}{81}}$ +... </div>произвольным образом вычеркнуты слагаемые. Докаж...

Докажите, что каждое целое число<i>A</i>представимо в виде<div align="CENTER"> <i>A</i> = <i>a</i>₀ + 2<i>a</i>₁ + 2²<i>a</i>₂ +...+ 2ⁿ<i>a</i>_n, </div>где каждое из чисел<i>a</i>_k= 0, 1 или -1 и<i>a</i>_k<i>a</i>_{k + 1}= 0 для всех0$\leqslant$<i>k</i>$\leqslant$<i>n</i>- 1, причем такое представление единственно.

Коля Васин задумал число от 1 до 200. За какое наименьшее число вопросов вы сможете его отгадать, если он отвечает на каждый вопрос а) да'' или нет''; б) да'', нет'' или ``не знаю''?

<b>Карточный фокус.</b>а) Берется колода из 27 карт (без одной масти). Ваш друг загадывает одну из карт. После чего вы раскладываете все карты в три равные кучки, кладя каждый раз по одной карте (в первую кучку, затем во вторую, затем в третью, потом снова в первую и т. д.). Ваш друг указывает на ту кучку, в которой лежит его карта. Далее вы складываете все три кучки вместе, вставляя при этом указанную кучку между двумя другими. Эта процедура повторяется еще два раза. На каком месте в колоде окажется загаданная карта, после того, как вы сложите вместе три кучки в третий раз? б) На каком месте окажется загаданная карта, если с самого начала было 3<i>n</i>(<i>n</i>< 9) карт?

Коля Васин задумал число от 1 до 31 включительно и выбрал из 5 данных карточек<div align="CENTER"> <table cellpadding="3" border="1"> <tr><td align="CENTER">1</td> <td align="CENTER">3</td> <td align="CENTER">5</td> <td align="CENTER">7</td> </tr> <tr><td align="CENTER">9</td> <td align="CENTER">11</td> <td align="CENTER">13</td> <td align="CENTER">15</td> </tr> <tr><td align="CENTER">17</td> <td align="CENTER">19</td> <td align="CENTER">21</td> <td align="CENTER">2...

Пусть<i>l</i>(<i>n</i>) — наименьшее число умножений, необходимое для нахождения<i>x</i>ⁿ. На примере чисел<i>n</i>= 15 и<i>n</i>= 63 покажите, что бинарный метод возведения в степень (смотри задачу<a href="https://mirolimp.ru/tasks/160902">5.64</a>) не всегда оптимален, то есть для некоторых<i>n</i>выполняется неравенство<i>l</i>(<i>n</i>) <<i>b</i>(<i>n</i>).

<b>Бинарный метод возведения в степень.</b>Предположим, что необходимо возвести число<i>x</i>в степень<i>n</i>. Если, например,<i>n</i>= 16, то это можно сделать выполнив 15 умножений<i>x</i>¹⁶=<i>x</i>^.<i>x</i>^....^.<i>x</i>, а можно обойтись лишь четырьмя:<div align="CENTER"> <i>x</i>₁ = <i>x</i>^.<i>x</i> = <i>x</i>²,    <i>x</i>₂ = <i>x</i>₁^.<i>x</i><sub&gt...

С числом разрешается производить две операции: увеличить в два раза'' и увеличить на 1''. За какое наименьшее число операций можно из числа 0 получить а) число 100; б) число<i>n</i>?

а) У одного человека был подвал, освещавшийся тремя электрическими лампочками. Выключатели этих лампочек находились вне подвала, так что включив любой из выключателей, хозяин должен был спуститься в подвал, чтобы увидеть, какая именно лампочка зажглась. Однажды он придумал способ, как определить для каждого выключателя, какую именно лампочку он включает, сходив в подвал ровно один раз. Какой это способ? б) Сколько лампочек и выключателей можно идентифицировать друг с другом, если разрешается 2 раза спуститься в подвал?

а) Имеются две веревки. Если любую из них поджечь с одного конца, то она сгорит за час. Веревки горят неравномерно. Например, нельзя гарантировать, что половина веревки сгорает за 30 минут. Как, имея две такие веревки, отмерить промежуток времени в 15 минут? б) Сколько промежутков времени (считая нулевой) можно отмерить, имея три такие веревки?

Вы имеете право сделать 4 гири любого веса. Какие это должны быть гири, чтобы на весах из предыдущей задачи можно было взвесить грузы от 1 до 40 кг?

Летела стая гусей. На каждом озере садилась половина гусей и еще полгуся. Остальные летели дальше. Все гуси сели на <i>n</i> озерах.

Сколько всего гусей было в стае?

Дан мешок сахарного песка, чашечные весы и гирька в 1 г. Можно ли за 10 взвешиваний отмерить 1 кг сахара?

Найдите последние три цифры периодов дробей ¹/₁₀₇, ¹/₁₃₁, ¹/₁₅₁. (Это можно сделать, не считая предыдущих цифр.)

Пусть число <i>m</i> имеет вид  <i>m</i> = 2^<i>a</i>5^<i>b</i><i>m</i>₁,  где  (10, <i>m</i>₁) = 1.  Положим  <i>k</i> = max {<i>a, b</i>}.

Докажите, что период дроби ¹/_<i>m</i> начинается с (<i>k</i>+1)-й позиции после запятой, и имеет такую же длину, как и период дроби ¹/_<i>m</i>₁.

Докажите, что не существует целых чисел, которые от перестановки начальной цифры в конец увеличивались бы в 5, 6 или 8 раз.