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

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

Докажите, что каждое целое число<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. За какое наименьшее число вопросов вы сможете его отгадать, если он отвечает на каждый вопрос а) да'' или нет''; б) да'', нет'' или ``не знаю''?

Пусть<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 кг сахара?