Un peu de combinatoire

Page 1 sur 2 1, 2  Suivant

Voir le sujet précédent Voir le sujet suivant Aller en bas

Un peu de combinatoire

Message par Phi le Mar 10 Juin - 17:19

Tiré du sujet du test de sélection de la délégation française de 1989 (retrouvé par hasard alors que j'étais chez mes grands parents, isolé, à travailler ma physique). C'était l'exercice 7.

Soit n dans N*.
On considère 3n+1 points dans le plan. Deux quelconques d'entre eux sont reliés par un segment coloré soit en bleu, soit en rouge, soit en blanc de telle sorte que de chaque sommet il part exactement n segments de chaque couleur.
1) Montrer qu'une telle construction est possible.
2) Montrer qu'elle contient forcément un triangle tricolore.

Bon courage!

Phi
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 75
Date d'inscription : 16/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Adrienmath le Mar 10 Juin - 19:29

Ton père faisait partie de la préparation olympique ? Sinon, les exos sont classés par ordre de difficulté ?
avatar
Adrienmath
Mouton noir au nirvana de la géométrie projective
Mouton noir au nirvana de la géométrie projective

Messages : 107
Date d'inscription : 31/03/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Phi le Mar 10 Juin - 19:44

Non, mon père ne faisait pas partie de la préparation, mais il a connu (en prépa) plusieurs de ceux qui l'avaient faite.
Je ne sais pas si les exos sont classés par ordre de difficulté. Je dirais que non, mais je te laisse en juger:

Exercice 1: montrer que
43/44 < S < 44/45 avec S=1/(2sqrt(1)+1sqrt(2))+1/(2sqrt(3)+3sqrt(2))+...+1/(1989sqrt(1988)+1988sqrt(1989))

[Facile quand on sait jouer avec des racines carrées]

Exercice 2: On pose S(n) comme la somme des i! pour i allant de 1 à n. Trouver tous les n tels que S(n) soit un carré parfait.

[Facile si on choisit le bon point de vue]

Exercice 3: L'équation t^3+at^2+bt+c=0 a trois solutions réelles, x>=y>=z.
Montrer a^2-3b>=0 et sqrt(a^2-3b)<=(x-z) (je ne suis pas sûr que la deuxième inégalité soit exactement ça mais ça implique bien chacun des deux membres, peut-être qu'il y a des constantes)

[Archi classique, mais pas sous cette forme]

Exercice 4: (Shortlist 1988) a est la suite définie comme suit:
-a(0)=0, a(1)=1
-a(n+2)=2a(n+1)+a(n)
Montrer que la valuation 2-adique de a(n) est la même que celle de n.

[Ma solution s'appuie sur une stratégie qui a l'air assez fréquente, sans la connaître ça doit être plus compliqué]

Exercice 5: ABC un triangle, I le centre du cercle inscrit, O celui du cercle circonscrit. On définit A' comme le centre du cercle circonscrit à IBC, B' et C' de même. Montrer que le triangle A'B'C' a O pour centre de son cercle circonscrit.

[D'un caractère classique indescriptible maintenant, mais en 1989?]

Exercice 6: (c'est celui dont je me souviens le moins bien et peut-être que je décris un exercice faux ou incomplet)
On a k personnes à une table ronde. Elles se lèvent, vont chercher un café puis se rassoient.
1) Si k=2n (n entier), montrer qu'il existe deux personnes qui seront à la même distance l'une de l'autre avant et après avoir cherché le café.
2) Que penser si k=7?

[Je ne l'ai absolument pas cherché.]

Exercice 7: celui que je vous ai soumis.


Dernière édition par Phi le Mar 10 Juin - 20:47, édité 2 fois

Phi
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 75
Date d'inscription : 16/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par baptiste collet le Mar 10 Juin - 20:37

une solution bourrine, étant donné les simplifications au cours du calcul il doit exister une solution plus élégante:
Spoiler:
1) la preuve par récurrence est simple
2)par l'absurde si aucun triangle n'était tricolore, tous contiendrait deux arêtes de même couleur issu d'un même sommet, en outre cette paire d'arête de même couleur n'est utilisé que par un seul triangle, il y en a :(3n+1)*3*"2 parmi n" or il y a "3 parmi 3n+1" triangles. on prouve par analyse-synthèse qu'il y a plus de triangle que de paires d'arête:
3n-1>3(n-1)
(3n+1)(3n-1)*3n/6>3*(3n+1)(n-1)*n/2
"3 parmi 3n+1">(3n+1)*3*"2 parmi n"
ce qui conclut

baptiste collet
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 49
Date d'inscription : 27/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par baptiste collet le Mar 10 Juin - 20:41

juste pour l'exercice 1, l'énoncé n'a pas l'air complet ni compréhensible.
mais merci pour ces exercices

baptiste collet
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 49
Date d'inscription : 27/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Phi le Mar 10 Juin - 20:46

Effectivement, je l'avais tapé mais il y a eu un problème quelque part. C'est corrigé.
Noter que le dernier terme de la somme est
1/(1988sqrt(1989)+1989sqrt(1988))

Phi
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 75
Date d'inscription : 16/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Phi le Mar 10 Juin - 21:01

Sinon, ta solution "bourrine" a l'air assez naturelle, contrairement à celle que j'ai trouvée (même si cette dernière ne nécessite presque aucun calcul).

Pour explorer la question 1, pouvez-vous donner une construction explicite?

Phi
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 75
Date d'inscription : 16/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par baptiste collet le Mar 10 Juin - 21:25

je trouve ces exercices plus facile que ceux de cette année c'est normal?
ex3:
les deux cas c'est relation de viète et inégalité du réordonnement,

baptiste collet
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 49
Date d'inscription : 27/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Phi le Mer 11 Juin - 6:53

C'est absolument normal, ça date de 1989, et c'était donc destiné aux lauréats du Concours général qui avaient au plus deux semaines d'expérience olympique.

Phi
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 75
Date d'inscription : 16/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Touveutoubé le Mer 11 Juin - 13:45

Pas très profond mais plutôt marrant (j'adooooore qd tout se télescope...) !

Ex 1:

De façon plus générale,
\begin{eqnarray*}
\sum_{k=1}^n \frac{1}{k \sqrt{k+1} + (k+1) \sqrt{k}} &=& \sum_{k=1}^n \frac{\sqrt{k+1}-\sqrt{k}}{(\sqrt{k+1}-\sqrt{k})(k \sqrt{k+1} + (k+1) \sqrt{k})} \\
&=& \sum_{k=1}^n \frac{\sqrt{k+1}-\sqrt{k}}{\sqrt{k(k+1)}} \\
&=& \sum_{k=1}^n \frac{1}{\sqrt{k}}-\frac{1}{\sqrt{k+1}} \\
&=& 1-\frac{1}{\sqrt{n+1}}
\end{eqnarray*}

Sinon, la géométrie est en effet très facile

Ex 5:

<AIB = 180-a/2-b/2 => <AC'B = a+b = 180-c => A,B,C,C' cocycliques.
De même, on en déduit que A,B,C,A',B' et C' sont cocycliques.
D'où ABC et A'B'C' ont même centre circonscrit.

Il restera les exos 4 et 2  Twisted Evil


Dernière édition par Touveutoubé le Mer 11 Juin - 14:50, édité 2 fois
avatar
Touveutoubé
Mouton à cinq pattes gardien du Saint Graal 42
Mouton à cinq pattes gardien du Saint Graal 42

Messages : 193
Date d'inscription : 29/03/2014
Localisation : 2^5-1

http://5.135.178.123:55/files/MOV_0197.mp4

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Adrienmath le Mer 11 Juin - 13:51

Phi a écrit:C'est absolument normal, ça date de 1989, et c'était donc destiné aux lauréats du Concours général qui avaient au plus deux semaines d'expérience olympique.

À l'époque (jusqu'en 1991 au moins) c'étaient des élèves de prépa et assez rarement des terminales qui participaient à l'OIM  Wink 

Plus que deux jours avant les vacances !!!!
avatar
Adrienmath
Mouton noir au nirvana de la géométrie projective
Mouton noir au nirvana de la géométrie projective

Messages : 107
Date d'inscription : 31/03/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Touveutoubé le Mer 11 Juin - 14:05

Adrienmath a écrit:
Plus que deux jours avant les vacances !!!!

Nous t'emmerdons cordialement (alement) !
avatar
Touveutoubé
Mouton à cinq pattes gardien du Saint Graal 42
Mouton à cinq pattes gardien du Saint Graal 42

Messages : 193
Date d'inscription : 29/03/2014
Localisation : 2^5-1

http://5.135.178.123:55/files/MOV_0197.mp4

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par baptiste collet le Mer 11 Juin - 14:06

merci de démoraliser ceux qui ont encore 2 semaines de cours Sad (mais à raison d'une heure de cours par jour c'est acceptable)
d'après l'autre, à l'époque les IMO étaient composées de plus d'exercices en moins de temps.

baptiste collet
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 49
Date d'inscription : 27/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par felixl le Mer 11 Juin - 14:32

Et ceux qui ont le bac Sad

Sépales, pétales, étamines, pistil. Anthères. Pollen.

felixl
Mouton noir au nirvana de la géométrie projective
Mouton noir au nirvana de la géométrie projective

Messages : 128
Date d'inscription : 29/03/2014

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Adrienmath le Mer 11 Juin - 14:34

Pas les IMO : regarde les vieux sujets ici https://www.imo-official.org/problems.aspx

Peut-être les tests de sélections français...

_________________
"Ne t'inquiète pas si tu as des difficultés en maths, je peux t'assurer que les miennes sont bien plus importantes !" Einstein.
avatar
Adrienmath
Mouton noir au nirvana de la géométrie projective
Mouton noir au nirvana de la géométrie projective

Messages : 107
Date d'inscription : 31/03/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Touveutoubé le Mer 11 Juin - 14:52

felixl a écrit:Et ceux qui ont le bac Sad

Sépales, pétales, étamines, pistil. Anthères. Pollen.

Voilà pourquoi il fallait prendre SI  afro 
avatar
Touveutoubé
Mouton à cinq pattes gardien du Saint Graal 42
Mouton à cinq pattes gardien du Saint Graal 42

Messages : 193
Date d'inscription : 29/03/2014
Localisation : 2^5-1

http://5.135.178.123:55/files/MOV_0197.mp4

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par felixl le Mer 11 Juin - 14:55

Y'a pas dans mon lycée ! À la place, on a des profs de maths qui font qu'on a quelqu'un qui a un prix aux olympiades académiques, et pas vous Wink

felixl
Mouton noir au nirvana de la géométrie projective
Mouton noir au nirvana de la géométrie projective

Messages : 128
Date d'inscription : 29/03/2014

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Touveutoubé le Mer 11 Juin - 15:03

Ta justification est tellement basse que je ne peux pas répondre  tongue 
avatar
Touveutoubé
Mouton à cinq pattes gardien du Saint Graal 42
Mouton à cinq pattes gardien du Saint Graal 42

Messages : 193
Date d'inscription : 29/03/2014
Localisation : 2^5-1

http://5.135.178.123:55/files/MOV_0197.mp4

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Phi le Mer 11 Juin - 16:57

Adrienmath: c'est logique, dans ce cas, puisque mon père avait raconté qu'il était meilleur en maths dans sa prépa que quelqu'un qui était probablement celui de qui il tient le test (puisque ladite personne avait fait l'IMO cette année-là, je crois).

Felixl: relargage. Lavage. Purification. Recristallisation. Distillation. CCM.
Ou dans la continuité de ton post: stigmate, style, gynécée. Androcée.
Ou alors: contingence. Nécessité. Finalité sans la représentation d'une fin. Absolu. Immatérialisme. Volonté de puissance. Désirs naturels et nécessaires, désirs vains. Mystique de la mécanique. Empirisme. Innéisme. [etc etc...]

Moi aussi j'aurais presque aimé prendre SI mais il n'y a pas ça dans mon lycée. Et tes profs de maths semblent être une pâle copie de ce qu'une classe de première de mon lycée a à subir (et que j'ai eu la chance de ne pas avoir!)

Déjà, elle est absolument rétive à toute solution qui diffère de la sienne. Ensuite, en contrôle, elle enlève la moitié des points au moins si on n'écrit pas mot pour mot sa solution. Enfin, il est un élève (brillant d'ailleurs, avec d'excellentes idées, tant en maths qu'en physique, mais qui est assez distrait—il n'a pas été pris à l'OFM parce qu'il a oublié de rendre la copie d'un exercice, il a lu "derrière" au lieu de "dernières" à l'exercice 5 de la Coupe Animath) dans sa classe qu'elle saque consciencieusement et arbitrairement.

Exemple 1: elle pose l'exercice suivant. Soit ABC un triangle équilatéral direct, on définit A' au tiers de AB en partant de A, B' au tiers de BC en partant de B, C au tiers de CA en partant de C. Montrer que A'B'C' est équilatéral.
Réponse de l'élève brillant susmentionné: on pose O centre du cercle circonscrit à ABC, la rotation directe de centre O et d'angle 120° envoie A', B', C' sur B', C', A', donc les triangles A'B'C' et B'C'A' sont semblables directement (dans cet ordre) et il s'ensuit que les angles A'B'C', B'C'A' et C'A'B' sont égaux donc égaux à 60° d'où la conclusion. [Rien de vraiment hors programme.]
Note: 0.

Exemple 2: dans un exercice conséquent sur le produit scalaire, un élève écrit vecteur a*vecteur b=0 et par distraction il ajoute une flèche sur le zéro.
Résultat: est perdue la moitié des points de l'exo. Tout ça pour une étourderie à une sous-question.

Bref, tout ça pour dire: ne vous plaignez jamais, on peut toujours trouver pire, et d'autres peuvent envier votre situation.

Phi
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 75
Date d'inscription : 16/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par felixl le Mer 11 Juin - 17:01

Mais moi je ne plaisantais pas.  Cool On a vraiment de bons profs de maths !

felixl
Mouton noir au nirvana de la géométrie projective
Mouton noir au nirvana de la géométrie projective

Messages : 128
Date d'inscription : 29/03/2014

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Phi le Mer 11 Juin - 17:04

Ah, j'ai complètement compris de travers alors. Au temps pour moi.

Phi
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 75
Date d'inscription : 16/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Touveutoubé le Mer 11 Juin - 18:06

Moi je ne peux pas juger mon prof de maths, car il faut dire que j'ai une écoute très...sélective de ce qu'il raconte  Rolling Eyes 
Sinon tu as vraiment de la chance Félix, mais moins de ne pas faire SI, car, à moins que mes impressions soient fausses, la SVT est quelque peu réduite au bachotage = voilà comment ça marche, vous l'apprenez, le récitez, réfléchissez un peu, faites des jolis schémas et nous serons contents ! Bien sûr je caricature volontairement mais ce qu'on apprend en SI me paraît qd même vraiment bcp bcp plus intéressant que la SVT, justification parmi tant d'autres, qui à mon sens est suffisante : on comprend vraiment ce qu'on fait, et on a des équations !!!! !!
Pour répondre à Phi, cette prof a l'air, du moins à tes dires, particulièrement exécrable et intolérante. Il faut ouvrir Freud et la psychanalyser => elle éprouve un manque de reconnaissance, son subconscient trouve dérangeant que certains de ses élèves aient des idées plus brillantes qu'elles, et donc...Bon je crois que je vais m'arrêter, j'espère seulement qu'elle n'a pas trop dégoûté l'élève en question, et qu'il a bien compris que cela ne se passe comme cela qu'au lycée (enfin normalement). Cela me fait penser à un autre (study) qui avait démontré le théorème de Pick [donc pas de parachutage] et qui l'avait ensuite utilisé parce qu'il n'avait pas envie de compter les petits carreaux, et avait reçu en récompense de son astuce une note très justifiée...
Mieux vaut ne pas continuer à parler des défauts de l'enseignement au lycée, car il y a à dire...
avatar
Touveutoubé
Mouton à cinq pattes gardien du Saint Graal 42
Mouton à cinq pattes gardien du Saint Graal 42

Messages : 193
Date d'inscription : 29/03/2014
Localisation : 2^5-1

http://5.135.178.123:55/files/MOV_0197.mp4

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par baptiste collet le Mer 11 Juin - 20:35

Touveutoubé a écrit:Il restera les exos 4 et 2  Twisted Evil
l'exercice 2 est trivial de toute façon, tu regardes les différentes valeur de S puis tu réalise que 5 divise toujours n! au-dessus de 5 et que donc S se finira toujours par 3, à partir de 4 or 3 n'est pas un carré modulo 10

baptiste collet
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 49
Date d'inscription : 27/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Phi le Mer 11 Juin - 20:39

Qui plus est j'ai eu trois ans de suite la même prof de SVT avec cet air sadique en commentant les contrôles (ratés, évidemment) et en se moquant de nos erreurs. On avait tous vraiment l'impression qu'elle était contente de mettre des sales notes.

L'élève en question est juste un peu paniqué pour son dossier (parce que ses notes de maths reflètent l'inverse de ses qualités mathématiques) mais il n'est heureusement pas traumatisé.

Baptiste: c'est exactement ce à quoi j'avais pensé.

Phi
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 75
Date d'inscription : 16/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par baptiste collet le Mer 11 Juin - 20:48

je m'en doutais mais je répondais à touveutoubé que l'exercice 2 était facile, en revanche j'ai réfléchi au 6 sans trouver

baptiste collet
Mouton de Panurge maître de la théorie des graphes
Mouton de Panurge maître de la théorie des graphes

Messages : 49
Date d'inscription : 27/05/2014
Age : 19

Revenir en haut Aller en bas

Re: Un peu de combinatoire

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Page 1 sur 2 1, 2  Suivant

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum