Физтех 2026/27 · Математика · 9 кл., №5 — решение · отбор · 1-я попытка

Условие

Сколько существует упорядоченных пар $(x;y)$ натуральных чисел, не превосходящих $40$ для которых произведение $xy$ является точным квадратом?

Дано: Натуральные $x, y$ с $1\le x\le 40$ $1\le y\le 40$ (границы включительно: «не превосходящих»). Пары упорядоченные: $(2;8)$ и $(8;2)$ считаются разными, пары вида $(x;x)$ тоже учитываются. Требуется число пар, для которых $xy$ — точный квадрат.

О задаче · 9 класс

Олимпиада: Физтех
Предмет / класс: Математика · 9 класс
Сезон / этап: 2026/27 · первый тур, первая попытка

Исследуй задачу

Модель с пояснениями к решениюОткрыть модель

Есть пояснения и построения из решения. Открой, когда захочешь воспользоваться этой помощью.

Исследование после решения

Сколько пар даёт граница N

Как растёт число упорядоченных пар (x;y) с квадратом xy, если менять верхнюю границу N? Сравните с «наивным» ответом ⌊√N⌋² — числом пар, в которых оба числа сами квадраты.

Верхняя граница N

Модель загружается…

Интерактив не заменяет доказательство критерия «xy — квадрат ⇔ одинаковые бесквадратные части»: он только показывает, как сумма c² растёт с N. Значение N ограничено 100, чтобы перебор бесквадратных чисел в браузере оставался мгновенным; формула верна для любого N.

Попробуйте самостоятельно. Найдите несколько пар, где ни $x$ ни $y$ не квадраты, а $xy$ — квадрат (например, $2\cdot 8 = 16$ ). Что общего у таких $x$ и $y$

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Подсказка 1

Посмотрите на разложение $xy$ на простые множители: произведение — точный квадрат тогда и только тогда, когда показатель каждого простого в нём чётен. Значит, важна не сама величина $x$ а чётность показателей в его разложении. Попробуйте «вынести» из $x$ наибольший квадрат и посмотреть, что останется: например, $12 = 3\cdot 2^2$ $40 = 10\cdot 2^2$

Подсказка 2

Запишите каждое число в виде $x = a\cdot k^2$ где $a$ не делится ни на какой квадрат, больший $1$ в $a$ соберите простые, входящие в $x$ в нечётной степени, а всё остальное — это $k^2$ Если $x = a k^2$ и $y = b m^2$ то $xy = ab\cdot(km)^2$ Остаётся выяснить: при каких бесквадратных $a$ и $b$ произведение $ab$ — квадрат?

Разобрать решение по шагам

Шаг 1. Бесквадратная часть числа

Любое натуральное $x$ записывается как $x = a\cdot k^2$ где $a$ — бесквадратное число (не делится ни на один квадрат простого). Чтобы получить такую запись, соберём в $a$ произведение всех простых, входящих в $x$ в нечётной степени; тогда в $x/a$ все показатели чётны, и это $k^2$ Запись единственна: если $x = a k^2$ с бесквадратным $a$ то простое $p$ делит $a$ ровно тогда, когда его показатель в $x$ нечётен, так что $a$ восстанавливается по $x$ однозначно.

Например, $12 = 3\cdot 2^2$ $40 = 10\cdot 2^2$ $36 = 1\cdot 6^2$ Число $a$ назовём бесквадратной частью $x$ Почему смотрим именно на него: условие « $xy$ — квадрат» зависит только от чётности показателей простых в $x$ и $y$ множитель $k^2$ на чётность не влияет, вся информация сидит в $a$

Шаг 2. Когда $xy$ — точный квадрат

Пусть $x = a k^2$ $y = b m^2$ с бесквадратными $a,b$ Тогда

xy = ab\cdot (km)^2,

и $xy$ — квадрат ровно тогда, когда $ab$ — квадрат.

Если $a = b$ то $ab = a^2$ — квадрат. Пусть $a\ne b$ Бесквадратное число — это произведение различных простых, поэтому оно однозначно задаётся множеством своих простых делителей; значит, у $a$ и $b$ эти множества различны, и найдётся простое $p$ делящее ровно одно из чисел $a$ $b$ Показатель $p$ в $ab$ равен $1$ — нечётный, и $ab$ не квадрат.

Итак, $xy$ — точный квадрат тогда и только тогда, когда у $x$ и $y$ одинаковые бесквадратные части: $a = b$

Шаг 3. Разбиваем числа $1,\dots,40$ на классы

Числа с бесквадратной частью $a$ — это $a\cdot 1^2,\ a\cdot 2^2,\ a\cdot 3^2,\dots$ , не превосходящие $40$ Их количество $c_a$ — наибольшее $k$ с $a k^2 \le 40$ то есть

c_a = \left\lfloor \sqrt{\dfrac{40}{a}}\,\right\rfloor.

Выписываем классы, в которых больше одного числа:

\begin{aligned} a=1&:\ 1,4,9,16,25,36\\[0.45em] a=2&:\ 2,8,18,32\\[0.45em] a=3&:\ 3,12,27\\[0.45em] a=5&:\ 5,20\\[0.45em] a=6&:\ 6,24\\[0.45em] a=7&:\ 7,28\\[0.45em] a=10&:\ 10,40 \end{aligned}

Значит, $c_1=6$ $c_2=4$ $c_3=3$ а для $a=5,6,7,10$ в классе по $2$ числа.

При $a \ge 11$ уже $4a > 40$ поэтому в классе только само $a$ Бесквадратные числа от $11$ до $40$ — это те, что не делятся ни на $4$ ни на $9$ ни на $25$ Их ровно $19$ 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39.

Каждое число попадает ровно в один класс (запись $a k^2$ единственна по шагу 1), и классы в сумме дают

6+4+3+4\cdot 2+19 = 40

чисел — контроль пройден.

Числа от 1 до 40, разложенные по классам с одинаковой бесквадратной частью a. В строке класса — числа a·1², a·2², …, справа размер класса c. Для a ≥ 11 класс состоит из одного числа — таких 19. Всего 6 + 4 + 3 + 4·2 + 19 = 40 чисел, каждое ровно в одном классе.

Шаг 4. Считаем упорядоченные пары

По шагу 2 пара $(x;y)$ подходит ровно тогда, когда $x$ и $y$ из одного класса. В классе из $c$ чисел упорядоченных пар (с учётом $x = y$ ) ровно $c\cdot c = c^2$ первый элемент выбирается $c$ способами, второй — независимо тоже $c$ способами.

Складываем по всем классам:

\begin{aligned} &6^2 + 4^2 + 3^2 + 4\cdot 2^2 + 19\cdot 1^2\\[0.45em] &= 36 + 16 + 9 + 16 + 19\\[0.45em] &= 96. \end{aligned}

Пары из разных классов не подходят, поэтому ничего не пропущено; а так как классы не пересекаются, ни одна пара не посчитана дважды.

Класс a = 2 целиком: таблица произведений xy для x, y ∈ {2, 8, 18, 32}. Все 4·4 = 16 клеток — точные квадраты, причём пары (x;y) и (y;x) — разные клетки, а диагональ даёт пары x = y. Так же в каждом классе получается c² пар; сумма по классам — 96.

Проверка

Проверка малым случаем. При $N=8$ классы $\{1,4\},\{2,8\},\{3\},\{5\},\{6\},\{7\}$ дают $4+4+1+1+1+1=12$ пар. Прямой перебор $64$ произведений находит ровно $12$ квадратов: $(1;1),(1;4),(4;1),(4;4)$ $(2;2),(2;8),(8;2),(8;8)$ и четыре пары $(x;x)$ для $x=3,5,6,7$

Проверка самого ответа. Полный компьютерный перебор всех $40^2=1600$ пар даёт $96$ квадратов, что совпадает с суммой

\sum_{a} \left\lfloor\sqrt{\dfrac{40}{a}}\right\rfloor^2 = 96

по бесквадратным $a\le 40$ Контроль размеров классов: $6+4+3+2+2+2+2+19=40$

Ответ

Главная идея

Произведение $xy$ — квадрат ровно тогда, когда у $x$ и $y$ одинаковая бесквадратная часть (после вынесения наибольшего квадрата остаётся одно и то же число). Поэтому числа $1,\dots,40$ разбиваются на непересекающиеся классы, а ответ — сумма квадратов размеров классов: $36+16+9+4\cdot 4+19=96$

Слова «произведение — точный квадрат» или « $xy$ — квадрат» — сигнал смотреть на чётность показателей простых. Как только условие зависит только от чётности, естественно «отбросить» квадратный множитель и работать с бесквадратной частью: числа распадаются на непересекающиеся классы, а счёт пар внутри классов — это сумма $c^2$ (или $C_{c}^{2}$ для неупорядоченных пар без совпадений).

Где легко ошибиться

Считать, что раз $xy$ — квадрат, то и $x$ и $y$ — квадраты, и отвечать $6^2 = 36$ (шесть квадратов $1,4,9,16,25,36$ ). Это неверно: $2\cdot 8 = 16$ $3\cdot 12 = 36$ $10\cdot 40 = 400$ — квадраты, хотя сомножители не квадраты. Квадратом должно быть только произведение бесквадратных частей, а не каждое число в отдельности.

Источник и авторство

Физтех · математика · 9 класс · 2026/27 · первый тур, первая попытка. Официальная задача 5.1 (ID 6085).

Официальные условия ↗ · Материалы организатора ↗

Подсказки, объяснение и исследовательские модели — Popov Academy. Решение проверено; результат сопоставлен с официальными материалами.

Тема, знания и приёмы

Делимость и простые множители · Нужна школьная база

Простые множители
Чётность показателей квадрата
Подсчёт упорядоченных пар

Приёмы решения: Разложение на множители · Последовательный подсчёт без повторов

Задать вопрос по задаче →