Олимпиадные задачи по теме «Системы счисления» для 11 класса - сложность 4 с решениями

Саша написал по кругу в произвольном порядке не более ста различных натуральных чисел, а Дима пытается угадать их количество. Для этого Дима сообщает Саше в некотором порядке несколько номеров, а затем Саша сообщает Диме в том же порядке, какие числа стоят под указанными Димой номерами, если считать числа по часовой стрелке, начиная с одного и того же числа. Сможет ли Дима заведомо угадать количество написанных Сашей чисел, сообщив

  а) 17 номеров;

  б) менее 16 номеров?

Фокусник с помощником собираются показать такой фокус. Зритель пишет на доске последовательность из <i>N</i> цифр. Помощник фокусника закрывает две соседних цифры чёрным кружком. Затем входит фокусник. Его задача – отгадать обе закрытые цифры (и порядок, в котором они расположены). При каком наименьшем <i>N</i> фокусник может договориться с помощником так, чтобы фокус гарантированно удался?

Расстоянием между числами  <span style="text-decoration: overline;"><i>a</i>₁<i>a</i>₂<i>a</i>₃<i>a</i>₄<i>a</i>₅</span>  и  <span style="text-decoration: overline;"><i>b</i>₁<i>b</i>₂<i>b</i>₃<i>b</i>₄<i>b</i>₅</span>  назовём максимальное <i>i</i>, для которого  <i>a_i</i> ≠ <i>b_i</i>.  Все пятизначные числа выписаны друг...

Саша написал на доске ненулевую цифру и приписывает к ней справа по одной ненулевой цифре, пока не выпишет миллион цифр. Докажите, что на доске не более 100 раз был написан точный квадрат.

Сколькими способами числа 2⁰, 2¹, 2&sup2, ..., 2²⁰⁰⁵ можно разбить на два непустых множества <i>A</i> и <i>B</i> так, чтобы уравнение  <i>x</i>&sup2 – <i>S</i>(<i>A</i>)<i>x + S</i>(<i>B</i>) = 0,  где <i>S</i>(<i>M</i>) – сумма чисел множества <i>M</i>, имело целый корень?

Существует ли такое натуральное число  <i>n</i> > 10¹⁰⁰⁰,  не делящееся на 10, что в его десятичной записи можно переставить две различные ненулевые цифры так, чтобы множество его простых делителей не изменилось?

Даны многочлены  <i>f</i>(<i>x</i>) и <i>g</i>(<i>x</i>) с целыми неотрицательными коэффициентами, <i>m</i> – наибольший коэффициент многочлена  <i>f</i>. Известно, что для некоторых натуральных чисел  <i>a < b</i>  имеют место равенства  <i>f</i>(<i>a</i>) = <i>g</i>(<i>a</i>)  и  <i>f</i>(<i>b</i>) = <i>g</i>(<i>b</i>).  Докажите, что если  <i>b > m</i>,  то многочлены  <i>f</i> и <i>g</i> совпадают.

Докажите, что для любого  <i>k</i> > 1  найдётся такая степень двойки, что среди <i>k</i> последних её цифр не менее половины составляют девятки.

(Например,  2¹² = ...96,  2⁵³ = ...992.)

Докажите, что первые цифры чисел вида 2^2ⁿ образуют непериодическую последовательность.

В королевстве 16 городов. Король хочет построить такую систему дорог, чтобы из каждого города можно было попасть в каждый, минуя не более одного промежуточного города, и чтобы из каждого города выходило не более пяти дорог.

  а) Докажите, что это возможно.

  б) Докажите, что если в формулировке заменить число 5 на число 4, то желание короля станет неосуществимым.

<i>N</i> друзей одновременно узнали <i>N</i> новостей, причём каждый узнал одну новость. Они стали звонить друг другу и обмениваться новостями.

Каждый разговор длится 1 час. За один разговор можно передать сколько угодно новостей.

Какое минимальное количество часов необходимо, чтобы все узнали все новости? Рассмотрите три случая:

  а)  <i>N</i> = 64,

  б)  <i>N</i> = 55,

  в)  <i>N</i> = 100.

Доказать, что сумма цифр числа<i>N</i>превосходит сумму цифр числа5^{5 .}<i>N</i>не более чем в 5 раз.

а) Доказать, что сумма цифр числа <i>K</i> не более чем в 8 раз превосходит сумму цифр числа 8<i>K</i>.

б) Для каких натуральных <i>k</i> существует такое положительное число <i>c_k</i>, что  <img align="absmiddle" src="/storage/problem-media/78791/problem_78791_img_2.gif"> ≥ <i>c_k</i>  для всех натуральных <i>N</i>? Найдите наибольшее подходящее значение <i>c_k</i>.

Рассматриваются всевозможные<i>n</i>-значные числа, составленные из цифр 1, 2 и 3. В конце каждого из этих чисел приписывается цифра 1, 2 или 3 так, что к двум числам, у которых во всех разрядах стоят разные цифры, приписываются разные цифры. Доказать, что найдется<i>n</i>-значное число, в записи которого участвует лишь одна единица и к которому приписывается единица.

Докажите, что числа вида 2ⁿпри различных целых положительных<i>n</i>могут начинаться на любую наперёд заданную комбинацию цифр.

Дан ряд чисел: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ..., в котором каждое число, начиная с третьего, равно сумме двух предыдущих. Найдётся ли среди первых  10⁸+ 1  членов этого ряда число, оканчивающееся четырьмя нулями?

Вычислите квадратный корень из числа 0,111...111<nobr>(100 единиц)</nobr>с точностью до<nobr>а) 100;</nobr><nobr>б) 101;</nobr><nobr>в)* 200</nobr>знаков после запятой.

Назовём натуральное число хорошим, если в его десятичной записи встречаются подряд цифры 1, 9,<nobr>7, 3,</nobr>и<nobr>плохим —</nobr>в противном случае. (Например, число<nobr>197 639 917 —</nobr>плохое, а<nobr>116 519 732 —</nobr>хорошее.) Докажите, что существует такое натуральное<nobr>число <i>n</i>,</nobr>что среди всех<i>n</i>-значных чисел<nobr>(от 10^{<i>n</i> – 1}</nobr>до<nobr>10^<i>n</i> – 1)</nobr>больше хороших, чем плохих.Постарайтесь найти возможно меньшее <nobr>такое <i>n</i>.</nobr>

В три сосуда налито по целому числу литров воды. В любой сосуд разрешено перелить столько воды, сколько в нём уже содержится, из любого другого сосуда. Докажите, что несколькими такими переливаниями можно освободить один из сосудов. (Сосуды достаточно велики: каждый может вместить всю воду.)

Король решил поощрить группу из $n$ мудрецов. Их поставят в ряд друг за другом (чтобы все смотрели в одном направлении), на каждого наденут чёрную или белую шляпу. Каждый будет видеть шляпы всех впереди стоящих. Мудрецы по очереди (от последнего к первому) назовут цвет (белый или чёрный) и натуральное число по своему выбору. В конце подсчитывается число мудрецов, которые назвали цвет, совпадающий с цветом своей шляпы: ровно столько дней всей группе будут платить надбавку к жалованью. Мудрецам разрешили договориться заранее, как отвечать. При этом мудрецы знают, что ровно $k$ из них безумны (кто именно – им неизвестно). Безумный мудрец называет белый или чёрный цвет и число вне зависимости от договорённостей. Какое максимальное число дней с надбавкой к жалованью могут гарантировать группе м...

Дано иррациональное число α,  0 < α < ½.  По нему определяется новое число α₁ как меньшее из двух чисел 2α и  1 – 2α.  По этому числу аналогично определяется α₂, и так далее.

  а) Докажите, что  α_<i>n</i> < ³/₁₆  для некоторого <i>n</i> .

  б) Может ли случиться, что  α_<i>n</i> > ⁷/₄₀  при всех натуральных <i>n</i>?

  Обозначим через <i>S</i>(<i>k</i>) сумму цифр натурального числа <i>k</i>. Натуральное число <i>a</i> назовём <i>n-хорошим</i>, если существует такая последовательность натуральных чисел <i>a</i>₀, <i>a</i>₁, ..., <i>a_n</i>, что  <i>a_n = a</i>  и  <i>a</i>_<i>i</i>+1 = <i>a_i – S</i>(<i>a_i</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. г) Докажите, что ни одно конечно слово из нулей и единиц не встречается в последовательности Морса три раза под...