2019-04-29
а) К хозяину гостиницы однажды пришел постоялец, не имевший денег, но обладавший серебряной цепочкой, состоящей из семи звеньев. Хозяин согласился держать этого постояльца неделю, при условии, что тот будет ему ежедневно отдавать в виде платы одно из звеньев цепочки. Какое наименьшее число звеньев надо распилить для того, чтобы владелец цепочки смог ежедневно в течение семи дней расплачиваться с хозяином (быть может, забирая у него при этом отданные ранее звенья и выдавая взамен их другие)?
б) Цепь состоит из 2000 звеньев. Какое наименьшее число звеньев надо распилить для того, чтобы любое число звеньев от 1 до 2000 можно было набрать, взяв некоторое число из образовавшихся частей?
Решение:
а) Достаточно распилить одно третье звено; при этом цепочка распадется на две части, содержащие соответственно 2 и 4 звена, и на одно отдельное (распиленное) звено. В первый день постоялец отдаст это звено; во второй - заберет его обратно и отдаст взамен часть цепочки, состоящую из двух звеньев; в третий - добавит снова распиленное звено; в четвертый - заберет все, что дал раньше, и передаст часть цепочки из четырех звеньев; в пятый - добавит еще раз распиленное звено; в шестой - возьмет обратно это звено и даст взамен часть цепочки из двух звеньев; в седьмой - отдаст последнее звено.
б) Удобно сначала разобрать следующую задачу: при каком наибольшем $n$ достаточно распилить $k$ звеньев $n$ - звенной цепи для того, чтобы любое число звеньев от 1 до $n$ можно было получить, взяв некоторые из образовавшихся частей цепи? Для решения этой задачи рассмотрим, каково наиболее выгодное расположение $k$ распиленных звеньев. Так как после перепиливания $k$ звеньев у нас будет $k$ отдельных (распиленных) звеньев, то любое число звеньев от 1 до $k$ мы сможем набрать уже только из них. Но $k+1$ звеньев мы уже не сможем получить, если у нас не будет части, состоящей из $k+1$ или менее звеньев. Ясно, что наиболее выгодно будет иметь часть точно из $k+1$ звеньев; тогда из этой части и $k$ отдельных звеньев мы сможем набрать любое число от 1 до $2k + 1$. Для того чтобы можно было получить также $2k + 2 = 2(k + 1)$ звеньев, нам надо будет иметь еще часть, содержащую $2(k+1)$ или менее звеньев; наиболее выгодно для нас будет, если эта часть будет содержать ровно $2(k+1)$ звеньев. Теперь мы можем уже составить все числа от 1 до $2k+1 + 2(k+1) = 4k + 3$; следующая по величине часть, которая нам необходима,- это часть, содержащая $4(k+1)$ звеньев. Продолжая рассуждать таким же образом, убедимся, что наиболее выгодным будет, если $k+1$ частей, получающихся после того, как мы распилили $k$ звеньев (отдельные $k$ звеньев, получающихся при этом, мы здесь не засчитываем в число частей), будут иметь соответственно следующие числа звеньев:
$k+1, 2(k+1), 4(k+1), 8(k + 1), \cdots, 2^k(k+1)$.
В этом случае любое число звеньев от 1 и до
$n = k+ {k+ 1 + 2 (k + 1) + 4 (k + 1) + \cdots + 2^k(k + 1)} = k+(2^{k + 1} - 1) (k+1) = 2^{k+1}(k + 1) - 1$
можно будет составить из частей цепи.
Итак, если $2^k k \leq n \leq 2^{k+1} (k + 1) - 1$, то можно обойтись $k$ разрывами цепи, но нельзя обойтись $k - 1$ разрывами. В частности,
при $2 \leq n \leq 7 \: k = 1$, при $160 \leq n \leq 383 \: k = 5$,
при $8 \leq n \leq 23 \: k = 2$, при $383 \leq n \leq 895 \: k = 6$,
при $24 \leq n \leq 63 \: k = 3$, при $896 \leq n \leq 2047 \: k = 7$,
при $64 \leq n \leq 159 \: k = 4$.
Итак, мы видим, что при $n = 2000$ наименьшее число распиленных звеньев равно 7. Условия задачи будут выполнены, если выбрать эти звенья так, чтобы получающиеся 8 частей цепи (7 отдельных звеньев мы здесь не считаем) имели соответственно 8, 16, 32, 64, 128, 256, 512 и 977 звеньев.
Ответ: а) Одно звено, б) 7 звеньев.