Отгадать день рождения

Задача

Уменье решать неопределенные уравнения дает возможность выполнить следующий математический фокус.

Вы предлагаете товарищу умножить число даты его рождения на 12, а номер месяца - на 31. Он сообщает вам сумму обоих произведений, и вы вычисляете по ней дату рождения.

Если, например, товарищ ваш родился 9 февраля, то он выполняет следующие выкладки:

 9 × 12 = 108, 2 × 31 = 62, 
            108 + 62 = 170. 

Это последнее число, 170, он сообщает сам, и вы определяете задуманную дату. Как?

Решение

Задача сводится к решению неопределенного уравнения

12x + 31y = 170

в целых и положительных числах, причем число месяца х не больше 31, а номер месяца у не больше 12.

 х = (170 - 31y)/12 = 14 - 3y + (2 + 5y)/12 = 14 - 3y + t, 

                      2 + 5y = 12t, 

 y = (-2 + 12t)/5 = 2t - 2 × (1 - t)/5 = 2t - 2t1, 

        1 - t = 5t1, t = 1 - 5t1, 

 y = 2(1 - 5t1) - 2t1 = 2 - 12t1, 

 x = 14 - 3(2 - 12t1) + 1 - 5t1 = 9 + 31t1. 

Зная, что 31 ≥ x > 0 и 12 ≥ y > 0, находим границы для t₁:

-9/31 < t1 < 1/6. 

Следовательно,

 t1 = 0, x = 9, у = 2.

Дата рождения 9-е число второго месяца, т. е. 9 февраля.

Можно предложить и другое решение, не использующее уравнений. Нам сообщено число а = 12х + 31у. Так как 12х + 24у делится на 12, то числа 7у и а имеют одинаковые остатки от деления на 12. Умножив на 7, найдем, что 49y и 7а имеют одинаковые остатки от деления на 12. Но 49у = 48у + у, а 48у делится на 12. Значит, у и 7а имеют одинаковые остатки от деления на 12. Иными словами, если а не делится на 12, то у равен остатку от деления числа. 7а на 12; если же а делится на 12, то y = 12. Этим число у (номер месяца) вполне определяется. Ну, а зная у, уже ничего не стоит узнать х.

Маленький совет: прежде чем узнавать остаток от деления числа 7а на 12, замените само число а его остатком от деления на 12 - считать будет проще. Например, если а = 170, то вы должны произвести в уме следующие вычисления:

     170 = 12 × 14 + 2 (остаток, значит, равен 2);
 
      2 × 7 = 14; 14 = 12 × 1 + 2 (значит, у = 2); 

 x = (170 - 31y)/12 = (170 - 31 × 2)/12 = 108/12 = 9 (значит, x = 9). 

Теперь вы можете сообщить товарищу дату его рождения: 9 февраля.

Докажем, что фокус всегда удается без отказа, т. е. что уравнение всегда имеет только одно решение в целых положительных числах. Обозначим число, которое сообщил ваш товарищ, через а, так что нахождение даты его рождения сводится к решению уравнения

12х + 31у = а.

Станем рассуждать "от противного". Предположим, что это уравнение имеет два различных решения в целых положительных числах, а именно решение х₁, y₁ и решение х₂, y₂, причем x₁ и х₂ не превосходят 31, а y₁ и y₂ не превосходят 12. Мы имеем:

 12x1 + 31y1 = a, 
 12х2 + 31у2 = а. 

Вычитая из первого равенства второе, получим:

12(x1 - х2) + 31 (у1 - у2) = 0.

Из этого равенства вытекает, что число 12 (x₁ - х₂) делится на 31. Так как x₁ и х₂ - положительные числа, не превосходящие 31, то их разность х₁ - х₂ по величине меньше чем 31. Поэтому число 12(x₁ - x₂) может делиться на 31 только в том случае, когда x₁ = x₂, т. е. когда первое решение совпадает со вторым. Таким образом, предположение о существовании двух различных решений приводит к противоречию.