|
|
 |
Условие
У Пети есть $60$ карточек с номерами от $1$ до $60$, на каждой написано действительное число. За один вопрос Вася может выбрать любые $17$ номеров и узнать у Пети сумму чисел на карточках с этими номерами. Может ли Вася гарантированно определить сумму чисел на всех $60$ карточках, задава) не более $30$ вопросов;
б) не более $20$ вопросов;
в) не более $10$ вопросов?
Решение
Первые два вопроса всегда тратим на $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\cdot4=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\cdot4=12$, как раз получится весь третий блок).
За 3 вопроса узнаём $3B + 2C$, проверяя каждый раз $9 + 8$ чисел — это все 9 чисел второго блока, и 8 чисел третьего, которые сдвигаем циклически ($3\cdot8=24$, так что третий блок будет подсчитан дважды).
Далее, сложив $9\cdot(A+C) +2\cdot(4A+4B+C) +3\cdot(3B+2C)$,
получим $17(A+B+C)$, и, поделив на 17, узнаем сумму этих 26 чисел.
В итоге мы потратили $2+1+4+3=10$ вопросов.
Замечания
Замечание 1. Родитель одного из участников, гроссмейстер и программист Дмитрий Яковенко нашёл способ узнать сумму 60 чисел всего за 9 вопросов. Вот его решение. Будем искать сумму всех 60 чисел, умноженную на 17. Можно считать, что у нас есть большой клетчатый прямоугольник высотой 17 и длиной 60, в котором в каждом горизонтальном ряду подряд стоят наши 60 чисел (в одном и том же порядке, каждое число занимает клетку) — то есть, каждому числу соответствует свой столбец (в котором 17 копий этого числа). Когда мы задаём вопрос о сумме каких-то 17 чисел, мы просто выбираем по клетке в 17 в соответствующих столбцах и, например, закрашиваем их. Наша цель — задать 9 вопросов так, чтобы закрасить весь прямоугольник (каждую клетку — ровно один раз). В конце останется сложить все полученные 9 ответов и поделить итог на 17.Первым вопросом узнаем сумму первых 17 чисел и сразу умножим её на 16 — то есть, закрасим большой кусок размером $16\times17$. У нас останется кусочек $1\times17$ из первых 17 чисел (отложим его, он нам пригодится в конце) и прямоугольник размерами $17\times43$. Ниже мы изобразили их на рисунке. Цифра, обведённая кружком, означает номер вопроса.
Третий вопрос: узнаём сумму следующих 17 чисел (с 35-го по 51-е) и умножаем её на 11.
Вопросы с 4-го по 8-й будут всегда включать в себя 9 оставшихся чисел (с 52-го по 60-е). То есть, к ним надо всегда добавлять ещё 8 чисел (и домножать сумму на необходимый нам множитель).
Например, четвёртым вопросом мы узнаем сумму 9 последних чисел плюс сумму 8 предыдущих, и умножим её на 6
Как видно из картинки, задав 7 вопросов, мы заполним практически весь прямоугольник $17\times43$: в нём останется незаполненным лишь правый верхний кусочек $1\times9$ из 9 последних чисел и кусочек $2\times4$, в котором по два раза записаны числа с 32-го по 35-е.
Разобьём отложенный кусочек $1\times17$ на две части: из 13 и из 4 чисел, и 8-м вопросом узнаем сумму этих 4 чисел, чисел с 32-го по 35-е (половинки кусочка $2\times4$) и правого верхнего кусочка $1\times9$. Наконец, 9-м вопросом найдём сумму 13 чисел отложенного кусочка и чисел с 32-го по 35-е (второй половинки кусочка $2\times4$). В итоге «закрашен» весь исходный прямоугольник $17\times60$.
Замечание 2. Интересно было бы узнать, за какое наименьшее число вопросов можно найти сумму всех 60 чисел (ответ жюри неизвестен).
Замечание 3. Интересно также, за какое наименьшее число вопросов можно узнать хотя бы одно из этих 60 чисел — например, записанное на первой карточке. Жюри умеет находить даже 3 числа за 8 вопросов. С другой стороны, за 18 вопросов можно узнать любые конкретные 18 чисел.
