Compréhension- exo principe des tiroirs
Cours gratuits > Forum > Forum maths || En basCompréhension- exo principe des tiroirs
Message de curio136 posté le 05-07-2020 à 18:07:28 (S | E | F)
Bonjour,
Voici un exemple de l'utilisation du principe des tiroirs trouvé dans un livre (Les olympiades des mathématiques Réflexes et stratégies 2ème édition, Tarik Belhadj Soulami, édition ellipses):
(Comme je ne sais pas utiliser les formules latex, j'utiliserai ci-dessous des parenthèses pour les indices et des crochets pour le plus petit entier supérieur à ...)
"Un grand maître joue au moins une partie d'échecs par jour pour garder la forme, mais pas plus de 10 par semaine pour ne pas se fatiguer. Prouver que s'il joue ainsi suffisamment longtemps, il y aura une période continue de jours pendant laquelle il aura joué exactement 21 parties.
Soit a(i) le nombre de parties disputées jusqu'au jour i inclus. On a alors
1 <= a(1) < a(2) <...< a(k) <= 10×[k/7] , k=1,2,...
On en déduit que
22 <= a(1)+21 < a(2)+21 <...< a(k)+21
<= 10×[k/7]+21 , k=1,2,...
Pour k suffisamment grand, l'inégalité 2k > 21+10×[k/7] devient vraie. Il s'ensuit qu'il existe deux indices i et j tels que a(j) = a(i)+21. Le grand maître aura alors disputé 21 rencontres pendant la période s'étalant entre le jour i +1 et le jour j inclus."
Pourrais t'on m'expliquer comment on aboutit à a(j) = a(i)+21
grâce à 2k > 21+10×[k/7]
Le lien m'échappe totalement...
Message de curio136 posté le 05-07-2020 à 18:07:28 (S | E | F)
Bonjour,
Voici un exemple de l'utilisation du principe des tiroirs trouvé dans un livre (Les olympiades des mathématiques Réflexes et stratégies 2ème édition, Tarik Belhadj Soulami, édition ellipses):
(Comme je ne sais pas utiliser les formules latex, j'utiliserai ci-dessous des parenthèses pour les indices et des crochets pour le plus petit entier supérieur à ...)
"Un grand maître joue au moins une partie d'échecs par jour pour garder la forme, mais pas plus de 10 par semaine pour ne pas se fatiguer. Prouver que s'il joue ainsi suffisamment longtemps, il y aura une période continue de jours pendant laquelle il aura joué exactement 21 parties.
Soit a(i) le nombre de parties disputées jusqu'au jour i inclus. On a alors
1 <= a(1) < a(2) <...< a(k) <= 10×[k/7] , k=1,2,...
On en déduit que
22 <= a(1)+21 < a(2)+21 <...< a(k)+21
<= 10×[k/7]+21 , k=1,2,...
Pour k suffisamment grand, l'inégalité 2k > 21+10×[k/7] devient vraie. Il s'ensuit qu'il existe deux indices i et j tels que a(j) = a(i)+21. Le grand maître aura alors disputé 21 rencontres pendant la période s'étalant entre le jour i +1 et le jour j inclus."
Pourrais t'on m'expliquer comment on aboutit à a(j) = a(i)+21
grâce à 2k > 21+10×[k/7]
Le lien m'échappe totalement...
Réponse : Compréhension- exo principe des tiroirs de tiruxa, postée le 06-07-2020 à 15:31:25 (S | E)
Bonjour
tous les a(i), i = 1 à k et tous les a(j)+21, j= 1 à k sont superieurs à 1 et STRICTEMENT inférieurs à 2k, soit 2k-1 entiers possibles pour 2k nombres entiers, les a(i) et les a(j)+21.
D'après le principe des tiroirs, il y a deux de ces entiers, au moins, qui sont égaux (dans le même tiroir), or ce ne sont pas les a(i) entre eux ni les a(j)+21 entre eux, donc il existe au moins un a(i) qui est égal à un a(j)+21.
Pour terminer cela se produit par exemple au bout de6 semaines, soit k=42.
Réponse : Compréhension- exo principe des tiroirs de curio136, postée le 06-07-2020 à 19:44:18 (S | E)
Merci beaucoup de votre réponse, maintenant je comprends bien mieux
Réponse : Compréhension- exo principe des tiroirs de tiruxa, postée le 08-07-2020 à 16:37:47 (S | E)
Juste une précision concernant la suite d'inégalités :
1 <= a(1) < a(2) <...< a(k) <= 10×[k/7] , k=1,2,...
Je ne suis pas d'accord sur les valeurs de k, en effet si on prend k=1 ou k=2.... ou k=6
on a alors [k/7]=0 et 10*[k/7]=0 et la suite d'inégalité est fausse car on a 1 à gauche et 0 à droite soit 0<1 !!
Par contre si on prend k= 7 pas de soucis 10*[k/7]=10 ce qui correspond aux données de l'énoncé (10 parties au plus par semaine),
de même pour k=14, on a 10*[k/7]= 20 ce qui est bien le nombre maximum de parties sur deux semaines.
Donc k doit être un multiple de 7 pour que la suite d'inégalités soit vraie.
Il faut écrire :
1 <= a(1) < a(2) <...< a(k) <= 10×[k/7] , k=7,14,...
oubien
1 <= a(1) < a(2) <...< a(k) <= 10×[k/7] , k/7=1,2,...
mais cela ne change pas la suite du raisonnement, puisqu'on utilise l'inégalité pour k/7=6 soit k=42.
Cours gratuits > Forum > Forum maths
