Поднебесное множество

[Ktina]

Назовём множество $\mathbb S$ поднебесным, если оно одновременно удовлетворяет следующим условиям:

1) Его элементами могут быть только натуральные числа в диапазоне $1\le n\le 100$
2) $\forall\quad a, b\in\mathbb S\quad\exists\quad c\in\mathbb S\quad :\quad (a, c)=(b, c)=1$
3) $\forall\quad a, b\in\mathbb S\quad\exists\quad d\in\mathbb S\quad :\quad (a, d)>1, (b, d)>1$

Какое наибольшее число элементов может быть в поднебесном множестве?

[hippie]

Ответ: 72.

{2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 14; 15; 16; 18; 20; 21; 22; 24; 25; 26; 27; 28; 32; 33; 34; 35; 36; 38; 39; 40; 44; 45; 46; 48; 49; 50; 51; 52; 54; 55; 56; 57; 58; 62; 63; 64; 65; 68; 69; 72; 74; 75; 76; 77; 78; 80; 81; 82; 85; 86; 87; 88; 91; 92; 93; 94; 95; 96; 98; 99; 100}

[Ktina]

hippie в сообщении #712715 писал(а):

Ответ: 72.

{2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 14; 15; 16; 18; 20; 21; 22; 24; 25; 26; 27; 28; 32; 33; 34; 35; 36; 38; 39; 40; 44; 45; 46; 48; 49; 50; 51; 52; 54; 55; 56; 57; 58; 62; 63; 64; 65; 68; 69; 72; 74; 75; 76; 77; 78; 80; 81; 82; 85; 86; 87; 88; 91; 92; 93; 94; 95; 96; 98; 99; 100}

А почему больше нельзя?

[hippie]

Абсолютно тупой перебор!

1 не может принадлежать множеству.
Если в множестве есть 2 различных простых числа, то есть и число кратное их произведению. Поэтому в нём не более одного простого числа большего 10. Остальные 20 простых чисел от 10 до 100 отсеиваются.

Для любого числа, входящего в множество, найдётся пара взаимно простых чисел, каждое из которых взаимно просто с данным.

Предположим, что 70 входит в множество. Тогда в него входят и числа $3p$ (или $9p$ ) и $q,$ где $p$ и $q\ -$ простые числа, большие 10. Тогда оно содержит и число не взаимно простое одновременно с $3p$ и $q,$ т.е. число $3q$ (или $9q$ ). Но тогда оно содержит и число взаимно простое одновременно с 70 и с $3q,$ т.е. второе простое число большее 10, что невозможно.
Аналогично отсеиваются числа 42, 84 и 30, 60, 90.

Таким образом искомое множество содержит не более 73 чисел, причём если оно содержит ровно 73 числа, то получается из приведённого мной множества
либо добавлением числа 66 (но тогда в нём нет числа взаимно простого одновременно с 66 и 35);
либо добавлением числа 66 и заменой 11 на 13 (и тогда в нём нет числа взаимно простого одновременно с 78 и 35).

[Ktina]

hippie в сообщении #712786 писал(а):

Абсолютно тупой перебор!

Вряд ли тупой перебор является единственным путём к решению.
Название темы сдержанно запускает шпильки касаемо страны, породившей задачу.