@MathIsFun

Есть такая задачка

Показать, что любой набор размером 201 из чисел с 1 по 299 будет иметь 2 числа, частное которых равно степени 3.

Всего существует 99 чисел, которые кратные 3 т.к. 3*99 = 297

Также существует 147 уникальных пар чисел частное которых равно степеням 3 так как:
99 чисел которые кратны трем, т.к. 3*99 = 297
33 чисел которые кратны девяти, т.к. 33 * 9 = 297
Аналогично
11 чисел кратных 27
3 кратных 81
1 кратное 243

Итого 99 + 33 + 11 + 3 + 1

Как идти дальше?

0

@kabenyuk

MathIsFun, Попробуйте так.
1) Рассмотрим граф Г, вершины которого - это числа от 1 до 299.
2) Считаем, что две вершины A и B смежны, если A/B - степень тройки ( с положительным или отрицательным показателем).
3) Каждая компонента связности этого графа является полным подграфом (докажите). Например, 1,3,9,27,81, 243.
4) Посчитаем сколько имеется полных подграфов в Г заданного порядка: 2, 3, 4, 5, 6. Это легко.
5) Теперь ваш вопрос переформулируем так. Сколько вершин надо удалить, чтобы в результате получился граф без ребер. Для этого надо иметь ввиду, что для полного графа порядка n придется удалить n-1 вершин.
6) Легкий подсчет показывает, что для того, чтобы лишить наш граф Г всех ребер надо удалить ровно 99 вершин.
Это и решит вашу задачу.

1

@MathIsFun

kabenyuk,

4) Количество подграфов в Г составляет 200, т. к. среди чисел от 1 до 299 ровно 200 чисел не являются кратным трем.

6) Каким образом можно это легко подсчитать? Я подозреваю, что нарисовав все 299 веришн, в этом можно убедиться. А как это сделать иначе, мне пока не совсем понятно.

0

iifat

Всего — 200. А по каждому порядку? Например, порядка 2 — сколько?

0

@kabenyuk

MathIsFun, слишком утомительно рисовать все 299 вершин. А вот нарисовать полный граф на шести вершинах будет полезно.
По поводу легко. Сколько существует полных подграфов порядка три, например. Вершины всякого такого графа выглядят так: k, 3k, 9k. Причем k не кратно 3 и k>11, иначе можно добавить к нему еще вершину. Ясно также, что k<33. Считайте.

0