[Principe Dirichlet] Joueur d'échec

[invited927d23c]

Bonjour,

Dans un livre traitant du principe de dirichlet je suis tombé sur l'exercice suivant :

Une personne joue au moins une partie par jour, mais pas plus de 10 par semaine. Démontrer qu'il existe une période continue de jours sur laquelle il aura joué 21 parties.

La solution donné est la suivante :

Soit le nombre de parties disputées jusqu'au jour i. Alors :



On déduit que :



Je ne comprend pas l'intêret d'additioner 21? Et ensuite je ne comprend plus ceci :

Pour k suffisament grand, l'inégalité devient vrai. Il s'ensuit qu'il existe deux indices i et j tels que .

Je n'arrive pas de suivre le raisonement de l'auteur. Et je ne vois pas comment il arrive à cette conclusion, et comment est utilisé le principe des tiroirs.

Merci d'avance pour toutes explications.
-----

[matthias]

Avec l'ensemble des ai et des ai+21 tu as 2k nombres entiers strictements positifs et tous inférieurs ou égaux à 10*ceil(k/7) +21.
Comme 2k > 10*ceil(k/7)+21, le principe de Dirichlet te dis qu'il y en a nécessairement deux qui sont égaux (2k nombres à ranger dans moins de 2k cases).
Or les ai sont tous distincts, de même que les ai+21 (strictements croissants), donc il existe i et j tels que aj=ai+21.

Ne reste plus qu'à trouver à partir de quel k ceci est vrai (pour le fun).

[invited927d23c]

Merci matthias pour l'explication .

J'ai enfin compris, je me demande combien de temps il m'aurait fallu pour le voir tous seul (j'aurais probablement abandonné avant). Maintenant que je sais comment il faut comprendre les explications de la résolution, tous paraît clair.

[matthias]

Il y a pas mal d'énigmes basées sur le principe de Dirichlet, et celle-là est assez classique, donc je ne me suis pas beaucoup foulé

En voici une autre dans un genre un peu différent :
On considère un entier strictement positif n, et n entiers relatifs A1, A2, ..., An.
Montrer qu'il existe p et q (1 <= p <= q <= n) tels que :
A(p) + A(p+1) + ... + Aq soit divisible par n.

[A voir en vidéo sur Futura]

[invited927d23c]

Bonjour,

J'ai recherché cette discussion car je ne me rappelais déjà plus comment on résolvais le problème du joueur d'échec (et j'avais pas envie de chercher).

Et j'en ai profité pour résoudre ton problème Matthias :

Je considère les sommes suivantes :



Si une d'entre elles est divisible par n c'est terminé. Sinon on prend les n restes des divisions , comme il n'y a que n-1 restes différents possible il y a forcément deux sommes (j<k) qui ont même reste. Alors est divisible par n.

Witten

[indian58]

Bonjour,

juste par curiosité, Witten, ce nbouquin ne serait-il pas par hasard le fameux livre bleu de Tarik Belhaj Soulami??

[invited927d23c]

Oui c'est bien ce livre là indian58. En l'achetant je pensais à quelque chose d'abordable (vu que c'est pour un "élève courageux de terminale"), mais généralement je patauge rien que pour comprendre les corrections .
Mais il sert bien en tant que dicitionnaire de théorèmes.

[indian58]

Je l'ai aussi ce bouquin et je suis d'accord avec toi quand l'auteur dit que c'est abordable par un "élève de terminale courageux". Il faut être vraiment courageux mais avec du temps, tu va bien assimiler le livre.