Олимпиадные задачи из источника «глава 5. Числа, дроби, системы счисления» для 11 класса
глава 5. Числа, дроби, системы счисления
НазадНайти все такие натуральные <i>n</i>, для которых числа <sup>1</sup>/<sub><i>n</i></sub> и <sup>1</sup>/<sub><i>n</i>+1</sub> выражаются конечными десятичными дробями.
<b>13 монет.</b>Предположим теперь, что имеется 13 монет, из которых одна — фальшивая. Как за три взвешивания на двухчашечных весах без гирь найти фальшивую монету, если не требуется выяснять, легче она или тяжелее настоящей?
<b>12 монет.</b>Из двенадцати монет одиннадцать настоящих, а одна фальшивая (она отличается по весу от настоящей, но не известно, в какую сторону). Требуется за три взвешивания на двухчашечных весах без гирь найти фальшивую монету и выяснить, легче она или тяжелее настоящей.
<b>Пешечное противостояние.</b>На доске 3×<i>n</i>расставлены<i>n</i>черных и<i>n</i>белых пешек так, как показано на рисунке:<div align="CENTER">
<img width="160" height="49" align="BOTTOM" border="0" src="/storage/problem-media/60920/problem_60920_img_2.gif" alt="\begin{picture}(100,30) \multiput(0,0)(0,10){4}{\line(1,0){100}} \multiput(0,0... ...5,5)(10,0){10}{\circle{5}} \multiput(5,25)(10,0){10}{\circle*{5}} \end{picture}">
</div>Пешки ходят и бьют по шахматным правилам, к которым добавляется одно: бить обязательно. Тот, кто не может сделать ход: а) выигрывает; б) проигрывает. Какой из игроков выигрывает в этой игре в зависимости от значения<i&...
Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять из одной кучки от 1 до 5 камней. Определите выигрышную стратегию в этой игре, если тот, кто взял последний камень а) выигрывает; б) проыигрывает.
<b>Игра ``Шоколадка''.</b>Имеется шоколадка, состоящая из6×8 = 48 долек. Одна из долек отмечена:<div align="CENTER">
$x$
</div>Двое игроков по очереди разламывают ее по какой-нибудь прямой, делящей шоколадку на дольки, и съедают ту половину, которая не содержит отмеченной дольки. Проигрывает тот, кто не может сделать хода, то есть ему остается лишь одна отмеченная долька. а) Опишите выигрышную стратегию в этой игре. Кто из игроков выиграет при данных начальных условиях? б) При каких размерах шоколадки начинающий игрок выигрывает при любом расположении отмеченной дольки? в) При каких размерах шоколадки начинающий игрок проигрывает при любом расположении отмеченной дольки?
Проанализируйте при помощи ним-сумм игру ``Йога''из задачи <a href="https://mirolimp.ru/tasks/160647">4.21</a>.
<b>Игра ``Ним''.</b>Имеется несколько кучек камней. Двое по очереди берут из них камни. За один ход разрешается взять любое (ненулевое) количество камней, но только из одной кучки. Выигрывает тот, кто взял последний камень. Для анализа игры каждому набору кучек камней<i>m</i><sub>1</sub>,<i>m</i><sub>2</sub>, ...,<i>m</i><sub>l</sub>поставим в соответствие его ним сумму (<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><sub>s</sub>...<i>m</i><sub>1</sub><i>m</i><sub>0</sub>)<sub>2</sub>, <i>k</i> = (<i>k</i><sub>s</sub>...<i>k</i><sub>1</sub><i>k</i><sub>0</sub>)<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><sub>m - 1</sub><i>b</i>&...
<b>Последовательность Морса.</b>Бесконечная последовательность из нулей и единиц<div align="CENTER"> 0110 1001 1001 0110 1001... </div>построена по следующему правилу. Сначала написан нуль. Затем делается бесконечное количество шагов. На каждом шаге к уже написанному куску последовательности приписывается новый кусок той же длины, получаемый из него заменой всех нулей единицами, а единиц — нулями. а) Какая цифра стоит на 2001 месте? б) Будет ли эта последовательность, начиная с некоторого места, периодической? в) Докажите, что данная последовательность переходит в себя при замене каждого нуля на комбинацию 01, а каждой единицы — на комбинацию 10. г) Докажите, что ни одно конечно слово из нулей и единиц не встречается в последовательности Морса три раза под...
<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>произвольным образом вычеркнуты слагаемые. Докаж...
<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...
Найдите последние три цифры периодов дробей <sup>1</sup>/<sub>107</sub>, <sup>1</sup>/<sub>131</sub>, <sup>1</sup>/<sub>151</sub>. (Это можно сделать, не считая предыдущих цифр.)
Пусть число <i>m</i> имеет вид <i>m</i> = 2<sup><i>a</i></sup>5<sup><i>b</i></sup><i>m</i><sub>1</sub>, где (10, <i>m</i><sub>1</sub>) = 1. Положим <i>k</i> = max {<i>a, b</i>}.
Докажите, что период дроби <sup>1</sup>/<sub><i>m</i></sub> начинается с (<i>k</i>+1)-й позиции после запятой, и имеет такую же длину, как и период дроби <sup>1</sup>/<sub><i>m</i><sub>1</sub></sub>.
Обозначим через <i>L</i>(<i>m</i>) длину периода дроби <sup>1</sup>/<sub><i>m</i></sub>. Докажите, что если (<i>m</i><sub>1</sub>, 10) = 1 и (<i>m</i><sub>2</sub>, 10) = 1, то справедливо равенство <i>L</i>(<i>m</i><sub>1</sub><i>m</i><sub>2</sub>) = [<i>L</i>(<i>m</i><sub>1</sub>), <i>L</i>(<i>m</i><sub>2</sub>)].
Чему равна длина периода дроби <sup>1</sup>/<sub><i>m</i><sub>1</sub></sub> + <sup>1</sup>/<sub><i>m</i><sub>2</sub></sub>?
Пусть (<i>m, n</i>) = 1. Докажите, что сумма длин периода и предпериода десятичного представления дроби <sup><i>m</i></sup>/<sub><i>n</i></sub> не превосходит φ(<i>n</i>).
Обозначим через <i>L</i>(<i>m</i>) длину периода дроби <sup>1</sup>/<sub><i>m</i></sub>. Докажите, что если (<i>m</i>, 10) = 1, то <i>L</i>(<i>m</i>) является делителем числа φ(<i>m</i>).
Число <i>N</i> = 142857 обладает и рядом других свойств. Например: 2·142857 = 285714, 3·142857 = 428571, ..., то есть при умножении на 1, 2, 3, ..., 6 цифры циклически переставляются; 14 + 28 + 57 = 99; <i>N</i><sup>2</sup> = 20408122449, 20408 + 122449 = 142857 = <i>N</i>.
Аналогичные операции можно проделывать и с другими периодами дробей. Что получается для чисел 1/17, 1/19? Объясните эти факты.
Периодом дроби <sup>1</sup>/<sub>7</sub> является число <i>N</i> = 142857. Оно обладает следующим свойством: сумма двух половин периода – число из одних девяток
142 + 857 = 999). Докажите в общем случае, что для простого <i>q</i> > 5 и натурального <i>p < q</i> период дроби <sup><i>p</i></sup>/<sub><i>q</i></sub> есть такое 2<i>n</i>-значное число <i>N</i> = <span style="text-decoration: overline;"><i>N</i><sub>1</sub><i>N</i><sub>2</sub></span>, что <i>N</i><sub>1</sub> + <i>N</i><sub>2</sub> = <img width="54" he...
Определим последовательности чисел (<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...
Дано <i>N</i> точек, никакие три из которых не лежат на одной прямой. Каждые две из этих точек соединены отрезком, и каждый отрезок окрашен в один из <i>k</i> цветов. Докажите, что если <i>N</i> > [<i>k</i>!<i>e</i>], то среди данных точек можно выбрать такие три, что все стороны образованного ими треугольника будут окрашены в один цвет.
Число <i>e</i> определяется равенством <img align="absmiddle" src="/storage/problem-media/60873/problem_60873_img_2.gif"> Докажите, что а) <img align="absmiddle" src="/storage/problem-media/60873/problem_60873_img_3.gif"> б) <img align="absmiddle" src="/storage/problem-media/60873/problem_60873_img_4.gif"> где 0 < <i>r<sub>n</sub></i> ≤ 1/<sub><i>n</i>!<i>n</i></sub>;в) <i>e</i> – иррациональное число.
Дан лист клетчатой бумаги. Докажите, что при <i>n</i> ≠ 4 не существует правильного <i>n</i>-угольника с вершинами в узлах решетки.