Задачки

Условие

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

Подсказка

Первым вопросом мы узнаем, что все числа 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₁₀ в столбик переносов не возникнет). Тем самым, мы однозначно определили загаданные числа за два вопроса.

МЦНМО