Question

Пожалуйста помогите решить! У березні 1532 року скупий лицар кожен день спускався до свого підвалу і додавав до (майже вже повної) скрині від 1 до 10 монет. Після цього він кожен раз підраховував монети і виявлялося, що число монет в скрині ділиться без остачі або на 22, або на 25 (але не на обидва ці числа відразу). Доведіть, що лицар збився з рахунку під час лічби своїх скарбів.

Answer 1

Відповідь:

Покрокове пояснення:

Оскільки лицар не може кинути туди 0 монет, бо за умовою він кидає від 1 до 10, то кількість монет завжди змінюється.  Подивимося, які числа в межах 100 діляться на 25. Це 25, 50, 75, 100. А на 22: 22,44,66,88.

Кількість монет не може ділитися завжди на 22, бо тоді йому б прийшлося кожного разу додавати 22 монети.

З цієї ж причини не може бути кожного разу 25, бо 25 не може він додавати за умовою.

Нехай спочатку було 25 монет. Щоб число ділилося на 22. він має додати 44-25=19 монет, тому ця ситуація не підходить, бо максимальна кількість 10 монет.

Розглянемо випадок, коли спочатку було число 22, тоді воно ділиться на 22, потім кидає 3 монети, і число ділиться на 25. Здавалося б, що він міг і не помилятися, але візьмемо інше число, яке ділиться на 22, наприклад 88, тоді наступного разу число має ділитися на 25, тобто наступне число 100. Знайдемо різницю між 100 і 88, 100-88=12, а 12 більше, ніж максимальна кількість монет, яку міг закинути чоловік.

Тому він помилявся!

Answer 2

Давайте розглянемо ситуацію ближче. Нехай n - кількість монет в скрині після того, як лицар додасть до неї монети. Ми знаємо, що n ділиться на 22 або 25, але не на обидва ці числа одночасно.

Виразимо це математично:

1. n ≡ 0 (mod 22) - n ділиться націло на 22.
2. n ≡ 0 (mod 25) - n ділиться націло на 25.

З врахуванням того, що 22 і 25 є взаємно простими числами (їхні найбільші спільні дільники дорівнюють 1), за теоремою китайської теореми про залишки:

Ми знаємо, що існує рішення для n, яке відповідає обом умовам одночасно. Тобто, існує така кількість монет, яка ділиться як на 22, так і на 25.

Це може статися лише в одному випадку: коли n ділиться на їхнє найменше спільне кратне (НСК) 22 і 25. НСК(22, 25) = 550.

Отже, n повинне бути кратним 550. Але умова задачі стверджує, що n додавалося до попереднього числа монет, яке було майже повним. Це означає, що n має бути в діапазоні від 1 до 10.

Але немає жодного числа в цьому діапазоні, яке є кратним 550.

Отже, суперечність доведена. Це означає, що припущення про те, що лицар може додавати монети до скрині щодня таким чином, щоб вона ділилася націло або на 22, або на 25, або на обидва числа, є помилковим. Тобто, лицар насправді збився з рахунку під час лічби своїх скарбів.