matematikk.net

La $A=\{1,2,3,...,2n\}$ der $n$ et et positivt heltall, og velg en vilkårlig delmengde $B$ bestående av $n+1$ elementer fra $A$.

Vis at det må finnes to tall i $B$ som er relativt primiske.

Mener å huske at denne var nevnt i boka My Brain is Open, som omhandlet Erdõs. Han presenterte denne oppgaven til Pósa over middag, og Pósa ga umiddelbart en løsning på tre ord:

[+] Skjult tekst

"Two are consecutive"

Pigeon hole principle ?

Jepp, riktig det: Anta det fins et utvalg på $n+1$ tall slik at ingen par er påfølgende heltall. Da må $|A|\geq n+1+n=2n+1>|A|$, som er motsigelsen.