Задание №176719: Турнир городов

6. У Пети есть 60 карточек с номерами от 1 до 60, на каждой написано действительное
число. За один вопрос Вася может выбрать любые 17 номеров и узнать у Пети сумму чисел на
карточках с этими номерами. Может ли Вася гарантированно определить сумму чисел на всех
60 карточках, задав
а) (3 балла) не более 30 вопросов;
б) (4 балла) не более 20 вопросов;
в) (5 баллов) не более 10 вопросов?
(Алексей Толпыго)

4

Ответ: может во всех трёх пунктах. Первые два вопроса всегда тратим на 17 + 17 = 34 числа и
узнаём их сумму, остаются 26 чисел.
а) Расположим оставшиеся 26 чисел по кругу и узнаем сумму каждых 17 подряд идущих из
них за 26 вопросов. Сложив эти 26 ответов и поделив на 17 (так как каждое число посчитано в

общей сумме 17 раз), мы узнаем сумму этих 26 чисел. И всю сумму тоже узнаем, прибавив первые
два ответа. В итоге мы потратили 2 + 26 = 28 вопросов.
б) Разобьём оставшиеся 26 чисел на два блока: из 9 и из 17 чисел. Пусть суммы в этих блоках
соответственно равны A и B. За один ход можно узнать B (выбрав весь второй блок). Теперь, как
в пункте а), расположим числа второго блока по кругу и далее за ход будем узнавать сумму 9
чисел первого блока и 8 подряд идущих чисел второго, каждый раз выбирая ещё не выбиравшиеся
8 подряд идущих чисел. Тогда за 17 вопросов, сложив полученные ответы, мы узнаем величину
17A+8B, так как во втором блоке мы переберём все возможные варианты 8 чисел, идущих подряд,

и каждое число второго блока в общей сумме будет посчитано 8 раз. Но слагаемое 8B нам известно,
откуда найдём A и потом A + B. В итоге мы потратили 2 + 1 + 17 = 20 вопросов.
Замечание. Есть много других вариантов разбиения 26 чисел на 2 блока, которые позволяют
уменьшить число вопросов. Например, разобьём их на два блока: из 10 чисел и из 16 чисел. Пусть
суммы в этих блоках соответственно равны A и B.
За 10 вопросов узнаем сумму A + 10B, проверяя каждый раз 1 + 16 чисел — по одному числу
первого блока и все 16 чисел первого блока.
За 4 вопроса узнаём 2A + 3B, проверяя каждый раз 5 + 12 чисел — это 5 чисел первого блока,

которые сдвигаем циклически, и 12 чисел второго блока, которые сдвигаем циклически (12·4 = 48,
то есть второй блок будет подсчитан трижды).
Далее, найдём B, вычислив 2(A + 10B) − (2A + 3B) и поделив на 17. После этого найдём и A
(например, вычтя 10B из суммы A + 10B). В итоге мы потратили 2 + 10 + 4 = 16 вопросов.
в) Разобьём оставшиеся 26 чисел их на три блока: из 5 чисел, из 9 чисел и из 12 чисел. Пусть
суммы в этих блоках соответственно равны A, B и C.
За 1 вопрос, взяв числа первого и третьего блоков, узнаём A + C.
За 4 вопроса узнаём 4A+4B+C, проверяя каждый раз 5+9+3 чисел — это все 5 чисел первого

блока, все 9 чисел второго блока и 3 числа третьего, которые сдвигаем циклически (3 · 4 = 12, как
раз получится весь третий блок).
За 3 вопроса узнаём 3B+2C, проверяя каждый раз 9+8 чисел — это все 9 чисел второго блока,
и 8 чисел третьего, которые сдвигаем циклически (3 · 8 = 24, так что третий блок будет подсчитан
дважды).
Далее, сложив 9 · (A + C) + 2 · (4A + 4B + C) + 3 · (3B + 2C), получим 17(A + B + C), и, поделив
на 17, узнаем сумму этих 26 чисел. В итоге мы потратили 2 + 1 + 4 + 3 = 10 вопросов.

Замечание 1. Интересно было бы узнать, за какое наименьшее число вопросов можно найти
сумму всех 60 чисел (ответ жюри неизвестен).
Замечание 2. Интересно также узнать, за какое наименьшее число вопросов можно узнать хотя
бы одно из этих 60 чисел — например, записанное на первой карточке. Жюри умеет находить это
число за 10 вопросов. С другой стороны, за 18 вопросов можно узнать любые конкретные 18 чисел.

7 (12 баллов). Дано натуральное k. На столе по кругу лежат n внешне одинаковых монет
массами 1, 2, ..., n г. Вам известно, что эти массы идут по порядку, но неизвестно, по часовой
стрелке или против, и с какого места начинаются. Одним взвешиванием разрешается сравнить
любые две монеты и узнать, какая тяжелее. Барон Мюнхгаузен утверждает, что вы можете
сделать k взвешиваний так, чтобы по их результатам гарантированно определить массу хотя
бы одной монеты. При каком наибольшем n слова барона будут правдой?
(Иван Митрофанов)


5

Ответ: n = 2 при k = 1 и n = 2k − 1 при остальных k.
Случай k = 1 очевиден. Далее разберём случай k > 1.
Алгоритм. Пусть n = 2k − 1. Пусть уже проведено несколько взвешиваний, нарисуем со-
ответствующие им стрелки (от меньшей монеты к большей). Будем считать, что монеты делят

окружность, на которой лежат, на равные промежутки длины 1 (а сами монеты — точки на этой
окружности).
Пусть монеты A,B,C,D расположены на окружности именно в таком циклическом порядке
−→ −−→
(возможно, A = D или B = C) и проведены стрелки AC и BD. Назовём зазором между этими
стрелками объединение дуг BC и DA, а длиной зазора — длину наибольшей из дуг BC и DA (дуги
берём «в том же циклическом порядке», то есть, например, дуга BC не содержит внутри точек
A и D). Докажем, что «разрыв» между монетами (граница между монетой массы 1 и монетой
массы n) расположен внутри зазора (то есть, на BC или DA).
В самом деле, пусть зазор расположен, например, на дуге CD.
Пройдём по окружности от монеты массой 1 до монеты массой n
(массы всё время будут возрастать).
В зависимости от направления, в котором идут монеты, мы в
одном случае пройдём сначала D, а потом B, что невозможно (так
как B < D), а в другом случае пройдём сначала C, а потом A, что
тоже невозможно (так как A < C). Противоречие. Аналогично,
разрыв не может быть на AB.

Теперь мы готовы описать сам алгоритм. Первые две стрелки выбираем «почти перпендику-
лярными», то есть так, чтобы четыре их конца делили окружность на дуги, длины которых не
больше чем 2k−2. Тогда длина зазора между ними будет тоже не больше чем 2k−2.
Докажем, что далее можно делать взвешивания так, чтобы ми-
нимальный зазор с каждым разом уменьшался хотя бы в два раза.
−→ −−→
Действительно, пусть зазор между AC и BD не превосходит 2a.
Пусть M — середина (или почти середина в случае нечётной дли-
ны) дуги BC, а N — середина (или почти середина) дуги DA. Если
−−→ −→
M < N, то зазор между MN и AC не превосходит 2a−1 (см. рису-
−−→ −−→
нок), а если N < M, это верно для зазора между NM и BD.
Действуя так, мы после k-го взвешивания найдём две стрелки с зазором не больше 1. Путь это
−→ −−→
AC и BD. Случаи B = C и A = D разбираются тривиально (в первом случае разрыв проходит
между лежащими рядом A и D, и так как A < C = B < D, то A = 1; во втором аналогично B = 1).
В случае различных A, B, C, D разрыв проходит между лежащими рядом A и D или между
лежащими рядом B и C, причём, так как A < C и B < D, все монеты на дуге AB легче, чем на
дуге CD. Но одна из этих дуг чётной длины (то есть с нечётным числом монет), и тогда монета,
лежащая посередине этой дуги, определяется однозначно.
Оценка. Предположим, что такой алгоритм есть при некотором n и за k взвешиваний мож-
но вычислить какую-то монету. Тогда после всех взвешиваний монеты могут быть расположены
не более чем двумя способами, и, произведя ещё одно взвешивание, мы узнаем полностью всю
конфигурацию. Но всего разных конфигураций 2n, а возможных результатов последовательности
из k + 1 взвешиваний — не более 2k+1. Итак, 2n (cid:54) 2k+1, откуда n (cid:54) 2k. Поэтому осталось лишь
доказать, что при n = 2k алгоритма нет.
Предположим противное, и есть какой-то алгоритм. Всего имеется 2k+1 возможных конфигу-
раций (того, как в действительности расположены монеты). Эти конфигурации бывают типа A
или B (по или против часовой стрелки). Здесь мы используем, что k > 1 (в случае двух монет нет


6

разницы между расположениями по и против часовой стрелки). После выполнения k взвешиваний
должны исключаться все конфигурации, кроме может быть двух: одной из A, второй из B. Тогда
в любой ситуации в конце должно оставаться ровно две конфигурации: одна из A, вторая из B.
Изначально, до взвешиваний, в A и B по 2k конфигураций. Несложно понять, что после каждого

взвешивания, вне зависимости от результата взвешивания, число возможных конфигураций из A
должно в точности уполовиниваться — иначе результаты следующих взвешиваний могут оказаться
такие, что в конце останется либо 0, либо больше одной конфигурации из A. То же верно и для B.
Нарисуем правильный n-угольник (вершины соответствуют монетам), каждую конфигурацию
типа A изобразим как красную сторону многоугольника (соединяющую монеты 1 и n). Каждая
конфигурация типа B — синяя сторона многоугольника (снова соединяющая монеты 1 и n). Из-
начально, когда имеется 2k+1 возможных конфигураций, каждая сторона «двойная» — проведена
и синим, и красным. Далее каждым ходом алгоритма выбираются две вершины, X и Y . Заметим,
что далее, в зависимости от ответа (кто из X, Y тяжелее), происходит одно из двух:

либо выкидываются синие стороны на дуге XY и красные на дуге Y X,
либо выкидываются синие стороны на дуге Y X и красные на дуге XY .
И, напомним, нам надо, чтобы каждый раз в любом случае число красных сторон уменьшалось
ровно вдвое, и число синих сторон уменьшалось вдвое.
Индукцией по i неcложно показать, что после i-го хода синие стороны будут образовывать дугу
длины 2k−i, а красные стороны — симметричную ей дугу. Переход индукции — несложным перебор
показываем, что следующее взвешивание должно затрагивать середины этих дуг.
Тогда после k взвешиваний останутся две противоположные стороны, одна красная, а другая
синяя. Но такие две конфигурации не имеют общих чисел, поэтому ни одно число восстановить

нельзя.

10 – 11 классы