Collier

Olympiades mathématiques, énigmes et défis
raptor77
Membre Rationnel
Messages: 813
Enregistré le: 27 Mai 2006, 06:48

Collier

par raptor77 » 02 Aoû 2006, 16:24

Bonjour On fabrique un collier (fermé) à l'aide de n perles blanches et n perles noires disposées dans un ordre arbitraire. Toute suite de m perles consécutives est appelée une m-chaîne.


Prouver que pour tout entier k tel que 1kn, il existe une 2k-chaîne contenant exactement k perles noires.

Prouver que si k -2 alors il existe même deux telles chaînes disjointes.

Bonne chance.
Gloire à la science.
Raptor.



raptor77
Membre Rationnel
Messages: 813
Enregistré le: 27 Mai 2006, 06:48

par raptor77 » 03 Aoû 2006, 14:49

ca fait 10h que j'attens une réponse :cry: :cry: :cry: :cry: :cry: :cry:

BiZi
Membre Relatif
Messages: 307
Enregistré le: 26 Mai 2006, 21:06

par BiZi » 03 Aoû 2006, 18:10

Ne sois pas si impatient, c'est dur ton exercice et aviateurpilot n'est pas là pour nous sauver la mise :ptdr:

raptor77
Membre Rationnel
Messages: 813
Enregistré le: 27 Mai 2006, 06:48

par raptor77 » 03 Aoû 2006, 18:47

Aviateur revient please!!

musichien
Membre Naturel
Messages: 35
Enregistré le: 02 Aoû 2006, 15:45

par musichien » 03 Aoû 2006, 19:25

apparemment que c'est super dur: Bruno Le Floch trouve pas pour le moment.:lol2:

BiZi
Membre Relatif
Messages: 307
Enregistré le: 26 Mai 2006, 21:06

par BiZi » 03 Aoû 2006, 21:04

musichien alias chaton> puisque tu me provoques, je m'engage à poster la réponse avant demain (enfin au moins la première question) :we: Prière donc à aviateurpilot de ne pas poster avant demain même s'il a trouvé :ptdr:

Je sens que je vais me ridiculiser si je trouve pas je vais devoir y passer la nuit :briques:

Alexa [Bot]
Membre Naturel
Messages: 83
Enregistré le: 15 Déc 2015, 16:13

par Alexa [Bot] » 03 Aoû 2006, 21:16


BiZi
Membre Relatif
Messages: 307
Enregistré le: 26 Mai 2006, 21:06

par BiZi » 03 Aoû 2006, 22:36

Euh effectivement on peut trouver les solutions des exos d'olympiades sur le net... Mais quel intérêt? :hum:

musichien
Membre Naturel
Messages: 35
Enregistré le: 02 Aoû 2006, 15:45

par musichien » 04 Aoû 2006, 10:07

(tiens, salut Igor!) En fait, je me suis trompé. C'est pas celui-là que j'ai demandé à Bruno le Floch. Et en plus, il paraît qu'il s'agissait d'un alter ego sur MSN ^^.
Quant à l'intérêt de chercher sur le net (c'est pas le net, c'est animath!^^), c'est pour ceux qui veulent la soluce. Et les autres sont pas obligés de regarder.

raptor77
Membre Rationnel
Messages: 813
Enregistré le: 27 Mai 2006, 06:48

par raptor77 » 04 Aoû 2006, 10:10

BiZi a écrit:musichien alias chaton> puisque tu me provoques, je m'engage à poster la réponse avant demain (enfin au moins la première question) :we: Prière donc à aviateurpilot de ne pas poster avant demain même s'il a trouvé :ptdr:

Je sens que je vais me ridiculiser si je trouve pas je vais devoir y passer la nuit :briques:



J'attens ta réponse Bizi

BiZi
Membre Relatif
Messages: 307
Enregistré le: 26 Mai 2006, 21:06

par BiZi » 04 Aoû 2006, 14:06

Il me reste un peu moins de neuf heures pour trouver :ptdr:

raptor77
Membre Rationnel
Messages: 813
Enregistré le: 27 Mai 2006, 06:48

par raptor77 » 04 Aoû 2006, 20:47

tic tac tic tac plus que 2h15 min

BiZi
Membre Relatif
Messages: 307
Enregistré le: 26 Mai 2006, 21:06

par BiZi » 04 Aoû 2006, 22:35

Bon en fait j'ai peut-être la réponse mais je crois que je vais pas avoir le temps de la recopier vu que je dois aller me coucher :we:

Supposons qu'il n'existe pas de 2k-chaîne contenant k boules noires. Découpons à présent le collier en E((2n/2k)) 2k chaînes, il y'a donc un résidu égal à n-E(2n/2k)*k perles.
Considérons les E((2n/2k)) 2k chaînes: puisque aucune de ces chaînes ne contient k boules noires, on en déduit que toutes ces chaînes contiennent k+r perles blanches, avec r un entier naturel supérieur ou égal à 2.

Or, on veut qu'il y'ait autant de perles blanches que de perles noires; par conséquent, en ne regardant que les E((2n/2k)) 2k chaînes, on voit qu'il y'a un excès de perles blanches de r*E((2n/2k)).

Il faut donc que le "résidu" contienne r*E((2n/2k)) perles noires de plus que de perles blanches.

Formons maintenant une autre 2k chaîne, avec le résidu et la suite de perles qui le cotoient: On rajoute ainsi au résidu 2k-(n-E(2n/2k)*k) afin d'obtenir la 2k chaîne voulue. Cette 2k chaîne, comme les autres, doit évidemment contenir au moins k+1 perles blanches.

Coupons-la maintenant en deux parties égales. Il y'a alors deux possibilités:

Soit la k-chaîne qui jouxte le résidu contient plus de E((k-r)/2)+1 boules noires, soit c'est l'autre partie qui contient plus de E((k-r)/2)+1 boules noires.

D'où n-E(n/k)*(k-r)<(k-r)/2

La suite demain :ptdr:

aviateurpilot
Membre Irrationnel
Messages: 1772
Enregistré le: 01 Juin 2006, 21:33

par aviateurpilot » 08 Aoû 2006, 11:46

soit (ou et
2)quelque soit i , (ou et } ou {}
pour i<j : c-à-dire l'un des deux passage {} ou {}

raptor77
Membre Rationnel
Messages: 813
Enregistré le: 27 Mai 2006, 06:48

par raptor77 » 08 Aoû 2006, 12:11

Exate aviateur

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 34 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite