Collier
Olympiades mathématiques, énigmes et défis
-
raptor77
- Membre Rationnel
- Messages: 813
- Enregistré le: 27 Mai 2006, 06:48
-
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 1

k

n, 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:
-
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 ,
)=> le nombre de perles noir le nombre de perles noir j)
(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
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 34 invités