Exercici 14 (Tasca 1).
(induction proof,
proof by cases,
hard exercise,
pigeonhole principle)
Divisibilitat en un conjunt de nombres
Demostreu que tot conjunt de n+1 naturals més petits o iguals que 2n, on n \ge 1, conté dos elements diferents a i b tals que a divideix b.
Ajut
Una possibilitat és fer servir el principi de les caselles: les cartes són els n+1 nombres i les caselles són els nombres senars entre 1 i 2n. Una carta de la forma 2^k d amb d senar es diposita en la casella d.
Una altra opció és considerar una demostració per inducció en n i distingir dos casos en el pas d’inducció: almenys un dels elements 2n+1 i 2n+2 no és al conjunt o tots dos hi són.