Petit problème d'arithmétique

[hussein515]

Bonjour,

Je sèche sur l'exo suivant:

Montrer que, parmi les entiers au plus égaux à 80, et strictement positifs, on ne peut en choisir 41 sans que, parmi ces 41 nombres, il en existe au moins deux tels que l'un soit multiple de l'autre.

Donc nous avons 41 nombres compris entre1 et 80, tous distincts et strictement supérieurs à 1 (sinon le problème est trivial) et qu'on peut supposer placés dans une liste ordonnée:



J'ai essayé de résoudre l'exo en divisant tous les entre eux: puis en sommant sur j, puis sur i, avec l’espoir d'arriver un jour à un Mais je n'arrive pas à avancer. Une petite indication me serait utile svp.

Merci !

hussein

[Ben314]

Salut.
Pour entier impair fixé, si on prend deux entiers distincts de la suite il y en a forcément un des deux qui divise l'autre donc si on veut choisir des entiers entre 1 et 80 (compris) sans qu'aucun ne soit multiple d'un autre, on ne peut prendre au plus qu'un seul entier dans chacune des suites de cette forme. Or des suites de cette formes, il y en a autant que de nombres impairs entre 1 et 80, c'est à dire 40.
(et c'est possible d'en prendre 40 en prenant systématiquement le dernier de chaque suite, c'est à dire en fait les nombres 41,42,43,...,80)

[hussein515]

Salut,

Waow. Très belle solution. Franchement j'aurais pas trouvé. Merci !

hussein