ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66636
Темы:    [ Делимость чисел. Общие свойства ]
[ Теория чисел. Делимость (прочее) ]
Сложность: 3
Классы: 6,7,8,9
В корзину
Прислать комментарий

Условие

На лицевой стороне каждой из $6$ карточек Аня написала черным или красным фломастером по натуральному числу. При этом каждым цветом Аня написала хотя бы два числа.

Затем Боря взял каждую карточку, посмотрел, каким цветом на ней написано число, перемножил все Анины числа того же цвета на других карточках и записал результат на обороте карточки (если другая карточка того же цвета всего одна, то Боря пишет число с этой одной карточки).

Мы видим обороты, на которых написаны числа $18$, $23$, $42$, $42$, $47$, $63$. А что написано на лицевых сторонах этих карточек?


Решение

Посмотрим на карточку с надписью «$23$». Пусть число на лицевой стороне этой карточки написано красным цветом. Тогда среди чисел красного цвета есть число, которое делится на $23$. Если чисел красного цвета хотя бы три, на оборотах должны быть хотя бы два числа, которые делятся на $23$, но это не так. Значит, чисел красного цвета ровно два и одно из них – на лицевой стороне карточки с числом $23$. Чёрным цветом тогда записаны четыре числа.

Аналогичные рассуждения можно провести с числом $47$: цвет числа на лицевой стороне карточки с числом $47$ встречается два раза, т.е. оно красное. Но тогда на лицевой стороне карточки с числом $23$ написано число $47$, а с числом $47$ – число $23$.

Разберёмся теперь с карточками, на которых Аня написала числа чёрным цветом. На их оборотах написаны числа $18$, $42$, $42$ и $63$. В их произведение $18\cdot 42\cdot 42\cdot 63=126^3$ каждое из чёрных чисел входит по три раза. Отсюда произведение чёрных чисел равно $126$. Тогда на лицевой стороне карточки с числом $18$ написано число $126/18=7$; с числом 42 – число $126/42=3$; с числом $63$ – число $126/63=2$.


Ответ

$7$, $47$, $3$, $3$, $23$ и $2$ соответственно.

Замечания

В решении мы воспользовались леммой Евклида: «если произведение нескольких чисел делится на простое число, то и хотя бы один из сомножителей делится на него». В решении важно, что числа 23 и 47 – простые.

Для составных чисел аналогичное утверждение неверно: для каждого составного числа $d$ можно придумать два числа $a$ и $b$, каждое из которых не делится на $d$, а их произведение делится. Например, ни число $2$, ни число $3$ не делится на $6$, а вот их произведение $2\cdot 3$ делится на $6$.

Лемма Евклида – пример не самого простого утверждения, доказательство которого, тем не менее, в школе опускается. А применение аналогичного утверждения для составных чисел – пожалуй, одна из самых частых ошибок при решении задач по теории чисел.

Подробнее про лемму Евклида и его алгоритм, а также основную теорему арифметики можно прочитать, например, в статье В.Н. Вагутен «Алгоритм Евклида и основная теорема арифметики» (журнал «Квант», 1972г., №6).

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

олимпиада
Название Турнир им.Ломоносова
номер/год
Год 2020
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .