Задача 35103

Темы:    [ Теория алгоритмов (прочее) ] [ Системы счисления (прочее) ]

Сложность: 4 Классы: 9,10,11

Условие

Один человек задумал 10 натуральных чисел - x₁, x₂, ... , x₁₀. Другой отгадывает их. Разрешается задавать вопросы вида: "чему равна сумма a₁x₁+a₂x₂+...+a₁₀x₁₀?", где a₁, a₂, ... , a₁₀ - некоторые натуральные числа. Как за 2 вопроса узнать все загаданные числа?

Подсказка

Первым вопросом мы узнаем, что все числа x₁, x₂, ... , x₁₀ меньше некоторой константы.

Решение

За первый вопрос узнаем значение выражения x₁+x₂+...+x₁₀. Пусть это значение равно С. Возьмем достаточно большое число n, такое что 10ⁿ>С. Вторым вопросом узнаем значение выражения x₁+10ⁿx₂+10²ⁿx₃+...+10⁹ⁿx₁₀. Если значение этого выражения равно S, то в десятичной записи числа S справа налево будут идти группы из n цифр, дающие десятичные записи чисел x₁, x₂, ... , x₁₀, возможно с несколькими нулями спереди (т.к. поскольку x₁, x₂, ... , x₁₀<10ⁿ, при сложении чисел x₁,10ⁿx₂,10²ⁿx₃,...,10⁹ⁿx₁₀ в столбик переносов не возникнет). Тем самым, мы однозначно определили загаданные числа за два вопроса.

Источники и прецеденты использования

web-сайт

задача