Больше целых дробей!

[Ktina]

Числа от 1 до 100 написаны на 100 различных карточках (по одному числу на карточке). Из этих карточек составляются 50 дробей. Какое наибольшее количество из этих дробей могут оказаться равными целым числам?

(по мотивам задачи И. С. Рубанова)

[arseniiv]

Интуитивно кажется, что жадный алгоритм, выбирающий поочерёдно из данной решётки данного частично упорядоченного множества (изначально $1..100$) по делимости какой-то максимум $M$ (кто-то, никого не делящий) и какой-то минимум $m$ (кто-то, ни на кого не делящийся) такие, что $m\mid M$, пока это возможно, и выплёвывающий дроби $M/m$, должен быть недалеко от оптимального. Доказать не берусь.

[Masik]

Это задача о максимальном паросочетании. Решается венгерским методом. Красивая задача!

[mihaild]

Только не венгерским - граф не двудольный. Но решается.

[12d3]

mihaild в сообщении #1252009 писал(а):

Только не венгерским - граф не двудольный. Но решается.

Алгоритмом Эдмондса решается. У меня вышло 44 пары.

[waxtep]

У меня получается максимум $43$ пары, перебором чисел от $100$ до $51$ в несколько проходов, на каждом проходе постоянна сумма показателей в разложении на простые множители:
- $10$ простых чисел, больших $50$, в любом случае останутся без пары;
- числа, большие $50$, у которых сумма показателей в разложении на простые равна $2$ ставим в пару с их наибольшим делителем, если он пока свободен (пример - $(95,19)$); иначе - с наименьшим, если он свободен (пример - $(65,5)$, поскольку $13$ уже занято в паре $(91,13)$); если и наименьший занят - этому числу не повезло (это числа $58,55,51$)
- далее четыре таких же прохода для сумм показателей от $3$ до $6$;
- в конце остается $13$ чисел $1,4,6,7,8,10,12,14,15,16,20,23,24$, из которых складывается $6$ пар, а одно число добавляется к числам-"неудачникам" $58,55,51$.
Доказать оптимальность не возьмусь.

[waxtep]

Можно $44$: разбил простые $p$ на группы, такие что $\frac{100}{n+1}<p\le\frac{100}n$. Для $n=3$ это будет $29$ и $31$ и, хочешь-не хочешь, придется "потратить" двойку и тройку, например $(3\cdot31,31), (2\cdot31,2), (2\cdot29,29), (3\cdot29,3)$ и т.д. по возрастанию $n$.

[waxtep]

Некоторое время думал, как внятно представить алгоритм и один из возможных результатов, видимо, можно так:

$$\begin{tabular}{lr|l|c|c} n & p & values & total & bad\\ \hline 1 & >50 & 97,89,83,79,73,71,67,61,59,53,1 & 11 & 9\\ 2 & 47,43,41,37 & \{47,43,41,37\}\times\{1,2\} & 8 & 0\\ 3 & 31,29 & \{31,29\}\times\{1,2,3\},2,3 & 8&0\\ 4&23&23\times\{(4,2)(3,1)\}&4&0\\ 5&19,17&\{19,17\}\times\{(4,2)(3,1),5\},5&11&1\\ 7&13&13\times\{(6,3)(5,1)(4,2),7\},7&8&0\\ 9&11&11\times\{(9,3)(8,4)(7,1)(6,2),5\}&9&1\\ 14&7&7\times\{(14,7)(12,6)(10,5)(9,3)(8,2),4\},4&12&0\\ 20&5&5\times\{(20,10)(18,9)(16,8)(15,5)(12,3)(4,2),6\},6&14&0\\ 33&3&3\times\{(27,9)(24,8)(18,6)(16,4)(12,3),32\},32&12&0\\ 50&2&64,16,8&3&1\\ \hline total & & &100&12 \end{tabular}$$