Test pour l'entrée en MPSI 2005 LLG

[invite4dc78ee9]

Hi,
possedez vous le corrigé du test d'entrée en MPSI à LLG, 2005 ?
Sinon, voila deux des difficiles exercices; comment les resoudre ?

1-On suppose que le plan est colori´e avec deux couleurs, par exemple bleu et rouge : chaque point
du plan est donc soit bleu soit rouge. Montrer que, quel que soit le coloriage, on peut toujours
trouver un triangle rectangle et isoc`ele dont les trois sommets sont de la mˆeme couleur.

2-Soit n > = 1 un entier. On dispose de n+2 objets distincts num´erot´es de 1 `a n+2 que l’on souhaite
ranger dans n tiroirs ´egalement num´erot´es de 1 `a n. De combien de mani`eres di´erentes cela
est-il possible sachant que chaque tiroir doit contenir au moins un objet ?

Merci
-----

[invitebfbf094d]

2-Soit n > = 1 un entier. On dispose de n+2 objets distincts num´erot´es de 1 `a n+2 que l’on souhaite
ranger dans n tiroirs ´egalement num´erot´es de 1 `a n. De combien de mani`eres di´erentes cela
est-il possible sachant que chaque tiroir doit contenir au moins un objet ?

Merci

Essayons de résoudre le deuxieme probleme. On a :

1 2 3 .... n boites
1 2 3 .... n n+1 n+2 objets

Chaque tiroir devant recevoir au moins un objet, cela signifie que chacune des n boites doit avoir un objet, il nous reste donc 2 objets a distribuer dans les n boites, lorsqu'on aura mis chacun des n objets dans les n boites. ON a donc :

1)n choix pour le 1er objet,
2)(n-1) choix pour le 2eme objet,
...
n)1 choix pour le dernier, le neme objet

Il nous reste deux objets, et on a n possibilités pour chacun, puisque les n boites ont deja leur objet. Finalement, on a au total : n+(n-1)+(n-2)+...+1+n+n possibilités differentes.

[invite21126052]

hmmm... je ne suis pas d'accord avec toi....

moi je vois ça comme ça:

on a n! façons de ranger n objets parmi n tiroirs
on a 2 parmi n+2 façons de choisir 2 objets parmi n+2
et on a 2 parmi n façons de choisir 2 tiroirs pour les 2 objets restants

finalement, on a n! * (2 parmi n+2) * (2 parmi n) façons de ranger n+2 objets dans n tiroirs, avec chaque tiroir ayant au moins un objet

je ne sais pas si c'est juste, mais ça ne peut pas être n+(n-1)+(n-2)+...+1+n+n possibilités, on est obligé de multiplier les "possibilités intermédiaires"....
en quelle classe vas tu entrer zapple ? tes idées étaient bonnes, mais il fallait multiplier, et non pas additionner

cela dit, je n'affirme pas que ma réponse soit la bonne non plus....!

[invitebfbf094d]

Qui donne n(n+5)/2 possibilités si je me trompe pas.

[A voir en vidéo sur Futura]

[invitebfbf094d]

finalement, on a n! * (2 parmi n+2) * (2 parmi n) façons de ranger n+2 objets dans n tiroirs, avec chaque tiroir ayant au moins un objet

Et ca donne combien au total une fois ton calcul fait ? Parce que j'ai essayé pour les cas n=3 et n=4 et mes calculs ont donné, semble t'il, la bonne réponse.

[invite21126052]

c'est de toute façon faux, car j'ai oublié le cas où l'on peut mettre 3 objets dans le meme tiroir!

donc je dirais en fait plutot:
n! * (2 parmi n+2) * n^2...

n! façons de ranger n objets dans n tiroirs
(2 parmi n+2) façons de choisir 2 objets parmi n+2
n*n façons de ranger 2 objets dans un choix de n boites...

pour n=3 je trouve 540 et pour n=4 je trouve 5760....

bien qu'en apparence élevé, ça me parait plausible...
j'essaye au papier, avec n=2...
je prévois 48 possibilités!

[invite19415392]

hmmm... je ne suis pas d'accord avec toi....

moi je vois ça comme ça:

on a n! façons de ranger n objets parmi n tiroirs
on a 2 parmi n+2 façons de choisir 2 objets parmi n+2
et on a 2 parmi n façons de choisir 2 tiroirs pour les 2 objets restants

Je vois pareil que toi, sauf que :
- Il faut diviser par 2, parce qu'avec ton calcul on tient compte symétriquement du cas où deux objets sont dans la même boîte parce que l'un ou l'autre a été choisi comme "objet supplémentaire".
- Enfin, il faut rajouter les cas où 3 objets sont dans la même boîte.

[invitebfbf094d]

Bah non, essaies de dessiner, pour le cas n=3, 3 boites, et 5 objets, puis tu fais les rangements. On trouve pas 540 possiblités

[invited5b2473a]

Pour la 1) c'est pas difficile: tu considères un un carré de côté 2, son centre et les centres des sous-carrés du grand carré. A toi ensuite de séparer les cas.



Pour la 2), tu va mettre 1 objet par case et ensuite tu vas caser les 2 derniers objets dans les n boîtes. Tu as donc (n+2)! * n^2 possibilités.

[invitebfbf094d]

Pour n=2, il est facile de ranger;on va le faire :

1)2 possibilités pour le 1er objet
2)1 possiblité pour le 2eme objet
3) reste 2 objets, chacune ayant 2 possibilités, soit 4 en tout.

Au total : 2+1+4=7 possiblités, ce que donne bien ma formule n(n+5)/2.

[invite21126052]

Pour n=2, il est facile de ranger;on va le faire :

1)2 possibilités pour le 1er objet
2)1 possiblité pour le 2eme objet
3) reste 2 objets, chacune ayant 2 possibilités, soit 4 en tout.

Au total : 2+1+4=7 possiblités, ce que donne bien ma formule n(n+5)/2.

bah j'en ai déjà au moins 12!
134 ____ 2
1 ____234
13 ____24
14 ____23
234 ____1
2 ____ 134
23 ____14
24 ____ 13
124 ____ 3
12 ____ 34
14 ___ 32
123 _____ 4

et c'est loin d'être fini...

par ailleurs, je suis d'accord que ma formule est fausse, il faut effectivement diviser... mais je me demande meme si ce n'est pas par 2*2... je vais y réfléchir

[invite19415392]

Sauf que là, tu donnes un ordre.
Pour n=2, à la main, je trouves 14 possibilités.
Les cas où 3 nombres sont dans la même boîte : 8 cas.
(1) ; (2,3,4) et son symétrique (2,3,4) ; (1)
(2) ; (1,3,4) ""
(3) ; (1,2,4) ""
(4) ; (1,2,3) ""

Les cas où il y a deux nombres par boîte : 6
(1,2) (3,4) et son symétrique (3,4) (1,2)
(1,3) (2,4) ""
(1,4) (2,3) ""

Total = 14 cas possibles.

[invite21126052]

j'ai une formule qui me donne 14:

n! * (2 parmi n+2) *[ (2 parmi n)*1/2 + n *1/3 ]
(disjonction des cas 2 objets séparés, et ensemble)

mais ça m'étonne qu'il ne faille diviser que par 2, et par par 4... puisqu'on a 2 objets à chaque fois qu'on peut considérer comme symétriques....

mais attention, les boites sont numérotées! donc on ne peut pas considérer les symétriques comme unique, comme tu l'as fait... à l'interieur des boites, oui, mais pas entre les boites elles memes...!

[invite19415392]

D'une manière générale :
- Cas où 3 nombres sont dans la même boîte :
Choisir la boîte : n
Choisir 3 parmi (n+2)
Répartir les n-1 restant parmi n-1 : (n-1)!
Total = n.C(3,n+2).(n-1)!
Application numérique pour n=2 : 2x4x1 = 8. Ok ^^

- Cas où il y a deux boîtes avec deux nombres :
Choisir les deux nombres "en excès" : C(2,n+2)
Placer les n "premiers nombres" : n!
Placer les deux derniers : n.(n-1)
Tenir compte de la symétrie : /4 (chaque combinaison est comptée 4 fois avec cette méthode)
Total : C(2,n+2).n!.n.(n-1)/4
Application numérique pour n=2 : 6x2x2x1/4 = 6 ; ok.

Total : n.C(3,n+2).(n-1)! + C(2,n+2).n!.n.(n-1)/4

[invite19415392]

mais attention, les boites sont numérotées! donc on ne peut pas considérer les symétriques comme unique, comme tu l'as fait... à l'interieur des boites, oui, mais pas entre les boites elles memes...!

Justement, c'est pour ça que je compte ce que j'appelle les symétriques dans cet exemple, c'est juste par flemme d'écrire deux fois la même chose dans un ordre différent ^^

[invite21126052]

oui, effectivement, pour placer les deux derniers, il faut un arrangement, pas une combinaison...

pour continuer avec ma méthode, je donne le résultat (qui apparemment correspond au tien!):

n! * (2 parmi n+2) * [ Arr(2 parmi n)*1/4 + n*1/3]

et avec n=3, on trouve 150...
et avec ta formule aussi!
je crois qu'on l'a eue...

et pour tes symétriques, d'accord, j'avais même pas remarqué que t'avais écrit 7 "couples" au lieu de 14!!

[invited5b2473a]

pour la 1) il y a plus simple que ce que j'avais proposé: il suffit de considérer deux carrés de côté 1 accolés et leur centre.

[invite4b9cdbca]

J'ai dû mal comprendre la première question, mais puisque c'est une surface qui est coloriée avec 2 couleurs, on suppose qu'on a plein d'aires de couleur(soit rouge soit bleu).
Dans ces aires on peut forcément dessiner soit un carré soit un cercle, d'où le triangle isocèle rectangle...
Mais je comprends pas le but de la question... Ai-je oublié un détail important ?

[invite19415392]

Rien ne dit que le coloriage soit propre (ie forme des beaux ensembles connexes) - par exemple, on peut avoir colorié en rouge les points dont au moins l'une des coordonnées est rationnelle, et en bleu les autres ...

[invite4b9cdbca]

Rien ne dit que le coloriage soit propre (ie forme des beaux ensembles connexes) - par exemple, on peut avoir colorié en rouge les points dont au moins l'une des coordonnées est rationnelle, et en bleu les autres ...

Mais peut on proprement parler de "colorier un point" sans tiquer ?

[invite5e34a2b4]

Mais peut on proprement parler de "colorier un point" sans tiquer ?

Si tu relis l'énoncé, tu vois bien qu'il est dit que chaque point est soit bleu, soit rouge. Donc, on colorie bien le plan point par point.
Bien évidemment que c'est impossible, mais les maths, c'est de la théorie, c'est pas comme la physique.
Et c'est surtout le raisonnement qui compte, raisonnement qu'on peut retrouver dans bien d'autres "théories", celles-là plus réelles.

[invite5e34a2b4]

Pour le 1), il y a quelque chose qu'on oublie souvent de faire. C'est de supposer/considérer quelque chose qui existe nécessairement. Bon, c'est sûr qu'ici, on peut y arriver sans, mais c'est quand même plus rapide avec.

En effet, on peut considérer dans ce plan 2 points A et B de la même couleur, par exemple rouge (même raisonnement s'ils sont bleus). De tels points existent nécessairement, car le plan constitué d'un nombre infini de points est colorié d'un nombre fini de couleurs (en l'occurrence 2).
Soient C et D, 2 points tels que ABCD soit un carré, et O le centre de ce carré.
2 possibilités s'offrent à nous :
. soit 1 des points C, D, O est rouge, et c'est joué.
. ou alors, C, D et O sont tous bleus et c'est aussi joué.

[invite21126052]

magnifique....

[invite4b9cdbca]

J'ai du mal a suivre...
Et s'il n'y a qu'un seul (ou deux) points rouge ?

[invite5e34a2b4]

J'ai du mal a suivre...
Et s'il n'y a qu'un seul (ou deux) points rouge ?

Fais-toi un petit schéma.

Bon, je ré-explique. J'ai le temps.

Le plan, constitué d'une infinité de points, est colorié d'un nombre fini de couleurs (en l'occurrence 2). Il existe donc nécessairement (au moins) 2 points, que l'on va appeler A et B, qui sont de la même couleur. Disons rouge. (même raisonnement s'ils sont bleus).

Considérons alors 2 points C et D, tels que ABCD soit un carré. Soit alors O, le centre de ce carré.

2 possibilités s'offrent à nous :
- soit au moins un des points C, D, O est rouge. On a donc notre triangle rectangle isocèle aux sommets de même couleur. (il s'agit du/des triangles AB+point rouge)
- ou alors aucun des points n'est rouge. C'est donc que C, D et O sont bleus. Or CDO est un triangle rectangle isocèle. CQFD.

T'as compris ?

[invite4b9cdbca]

Ah oui c'est bon, je suis un peu lent désolé
Forcément s'il y a qu'un point rouge tout le reste est bleu... Donc plein de points bleus...
Oula c'était trop pour moi maintenant j'ai des visions de carrés à pois rouge et bleus...