deelverzamelingen

Opgave - NWO 1993 vraag 1

$V$ is de verzameling getallen $\{1,2,3,\ldots,24,25\}$.
a) Laat zien dat uit $V$ een deelverzameling van 16 getallen gekozen kan worden waarvoor geldt dat het product van geen enkel tweetal getallen uit die deelverzameling het kwadraat van een geheel getal is.
b) Laat zien dat elke deelverzameling van $V$ met 17 of meer elementen een tweetal getallen bevat waarvan het product een kwadraat van een geheel getal is.

Oplossing

$a)$ neem bijvoorbeeld de deelverzameling $\{1,2,3,5,6,7,10,11,13,14,15,17,19,21,22,23\}$

We leggen even uit waarom dit werkt:
de verzameling bevat enkel getallen van de vorm $1$, $p$, $pq$ waarbij $p$ en $q$ verschillende priemgetallen zijn.
Een volkomen kwadraat bevat een even aantal priemfactoren.
Indien we een tegenvoorbeeld hebben, is dit dus van de vorm $1*pq$, $p_1*p_2$ of $p_1q_1*p_2q_2$ en daar we verschillende getallen nemen zal geen enkel getal van deze vorm een volkomen kwadraat zijn. ( want dat zou impliceren dat $p_1=p_2$ etc)

$b)$

Bekijk de disjucte verzamelingen $\{1,4,9,16,25\}$, $\{2,8,18\}$ , $\{3,12\}$, $6,24\}$ en $\{5,20\}$.
Uit iedere verzameling kan maximaal $1$ element gekozen worden, aangezien het product van $2$ elementen uit iedere verzameling een volkomen kwadraat oplevert.
Dit betekent dat er resp. min. $4,2,1,1,1$ getallen niet mogen worden gekozen.
dat zijn $9$ getallen die er niet in mogen. nu het zware rekenwerk: $25-9=16$! dus $16$ is het maximale aantal elementen van de deelverzameling $\blacksquare$