Вопрос школьника
Кошик наповнений яблуками. Якщо їх виймати по 2, по 3. по 4. по 5 чи
по 6 . то в кошику залишатиметься щоразу по одному яблуку. Скільки яблук
у кошику, якщо він може вмістити не більше 1 0 0 яблук?
Ответ от учителя
Для розв’язання цієї задачі потрібно скористатися китайською теоремою про лишки.
За умовою задачі, якщо виймати яблука по 2, 3, 4, 5 або 6, то в кошику залишатиметься по одному яблуку. Це означає, що кількість яблук у кошику є на 1 більшою за кожне з чисел 2, 3, 4, 5 і 6.
Позначимо кількість яблук у кошику як N. Тоді ми можемо записати наступну систему рівнянь:
N ≡ 1 (mod 2)
N ≡ 1 (mod 3)
N ≡ 1 (mod 4)
N ≡ 1 (mod 5)
N ≡ 1 (mod 6)
Застосуємо китайську теорему про лишки, щоб знайти розв’язок цієї системи.
Спочатку знайдемо добуток всіх чисел, що входять у систему:
M = 2 × 3 × 4 × 5 × 6 = 720
Тепер знайдемо числа Mi, які є добутками всіх чисел, крім i-го числа у системі:
M2 = 3 × 4 × 5 × 6 = 360
M3 = 2 × 4 × 5 × 6 = 240
M4 = 2 × 3 × 5 × 6 = 120
M5 = 2 × 3 × 4 × 6 = 180
M6 = 2 × 3 × 4 × 5 = 120
Далі знайдемо обернені числа mi за модулем Mi. Це можна зробити за допомогою розширеного алгоритму Евкліда:
m2 = 2
m3 = 3
m4 = 1
m5 = 4
m6 = 1
Тепер знайдемо розв’язок системи за формулою:
N = a1M1m1 + a2M2m2 + a3M3m3 + a4M4m4 + a5M5m5 + a6M6m6
де ai = 1 для кожного рівняння у системі.
Підставляючи значення, отримуємо:
N = 1 × 360 × 2 + 1 × 240 × 3 + 1 × 120 × 1 + 1 × 180 × 4 + 1 × 120 × 1 = 1741
Отже, у кошику міститься 1741 яблуко.
Проте, за умовою задачі, кошик може вмістити не більше 100 яблук. Тому правильна відповідь на задачу — 91 яблуко (1741 — 17 × 100 = 91).
