|
#1 - 28-07-2013 20:08:45
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
amateurs de boules, en mode jardcore !
1) Vous avez 40 boules face à vous dont une seule est d'un poids différent des autres. Comment la retrouver en un nombre minimum de pesées ?
2) Idem avec 121 boules !
3) Idem avec un nombre n quelconque de boules.
#2 - 28-07-2013 20:16:51
- MthS-MlndN
- Hors d'u-Sage
- Enigmes résolues : 49
- Messages : 12,414E+3
- Lieu: Rouen
Amateurs de boules, en mde hardcore !
Le titre est douteux, et le problème pas à ma portée ^^
Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
#3 - 28-07-2013 21:01:23
- Lui-meme
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 2762
- Lieu: Île de France
Amateurs de boules, en mode hardcoore !
Dis donc titoufred, t'as reçu un stock de boules que t'essayes d'écouler?
#4 - 28-07-2013 23:33:24
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
amateurs se boules, en mode hardcore !
Mathias, je comprends que la vue simultanée de 40 boules puisse effrayer la première fois, mais je t'assure que ce n'est vraiment pas la mer à boire.
#5 - 29-07-2013 10:00:36
- kossi_tg
- Professionnel de Prise2Tete
- Enigmes résolues : 18
- Messages : 307
- Lieu: Montargis
amateurs de boules, en mode hzrdcore !
1-) 40 boules *** 1ère pesée: 10 boules sur chaque plateau Si il y a égalité alors la boule intruse fait partie de l'autre moitié c'est à dire les 20 boules non pesées; sinon elle fait partie des 20 pesées. A ce niveau, j'ai 20 "bonnes" boules à coup sûr (notées du groupe A) et 20 autres incluant l'intruse (notées du groupe B1).
*** 2ème pesées: 10 boules de A sur un plateau et 10 boules de B1 sur l'autre plateau Si il y a égalité alors la boule intruse fait partie de l'autre moitié de B1 c'est à dire les 10 boules de B1 non pesées; sinon elle fait partie des 10 pesées de B1. J'ai alors 10 boules incluant l'intruse (notées du groupe B2).
*** 3ième pesée: 5 boules de A sur un plateau et 5 boules de B2 sur l'autre plateau Si il y a égalité alors la boule intruse fait partie de l'autre moitié de B2 c'est à dire les 5 boules de B2 non pesées; sinon elle fait partie des 5 pesées de B2. J'ai alors 5 boules incluant l'intruse (notées du groupe B3).
*** 4ième pesée: 3 boules de A sur un plateau et 3 boules de B3 sur l'autre plateau Si il y a égalité alors la boule intruse fait partie des 2 boules de B3 non pesées; sinon elle fait partie des 3 pesées de B3. J'ai alors 2 ou 3 boules incluant l'intruse. Pour être dans la situation la plus défavorable, je vais supporter avoir 3 boules incluant l'intruse (notées du groupe B4).
*** 5ième pesée: 2 boules de A sur un plateau et 2 boules de B4 sur l'autre plateau Si il y a égalité alors la boule intruse est trouvée, elle est la dernière boule non pesée de B4; sinon elle fait partie des 2 pesées de B4 (notées du groupe B5).
*** 6ième pesée: 1 boule de A sur un plateau et 1 boule de B5 sur l'autre plateau Si il y a égalité alors la boule intruse est la dernière boule non pesée de B5; sinon elle est la boule pesée de B5.
Bref, la boule intruse est trouvée en 6 pesées maximum.
2-) 121 boules *** 1ère pesée: 30 boules sur chaque plateau Si il y a égalité alors la boule intruse fait partie des 61 boules non pesées; sinon elle fait partie des 60 pesées. A ce niveau, j'ai 60 ou 61 "bonnes" boules à coup sûr (notées du groupe A) et 61 ou 60 autres incluant l'intruse (notées du groupe B1). Cas le plus dévaforable; B1 contient 61 boules et A en contient 60.
*** 2ième pesée: 31 boules de A sur un plateau et 31 de B1 sur l'autre l'autre plateau . . .(même processus que pour les 40 boules).
Bref, la boule intruse sera trouvée en 7 pesées maximum.
3-) Cas général de n boules Soit PE(x) la fonction partie entière. *** 1ième pesée: Soit n0=PE(x/4). n0 boules sur chaque plateau Si il y a égalité alors la boule intruse fait partie des (n-2*n0) boules non pesées; sinon elle fait partie des 2*n0 pesées. A ce niveau, j'ai (n-2*n0) ou 2*n0 "bonnes" boules à coup sûr (notées du groupe A) et (n-2*n0) ou 2*n0 autres incluant l'intruse (notées du groupe B1). Cas le plus dévaforable; B1 contient MAX{(n-2*n0);2*n0} boules et A en contient MIN{(n-2*n0);2*n0}.
*** 2ième pesée: . . .(même processus que pour les 40 boules).
Bref, la boule intruse sera trouvée en N pesées où N=1+PE(P) et P=ln(n)/ln(2).
#6 - 29-07-2013 12:55:40
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Amateurs de boules, en mode hardore !
kossi_tg a écrit:10 boules de A et 10 boules de B1 sur chaque plateau Si il y a égalité alors la boule intruse fait partie de l'autre moitié de B1 c'est à dire les 10 boules de B1 non pesées
"sur chaque plateau", comme il y en a deux, ça fait 40 boules pesées donc il n'y a pas de boule non pesée. Il y a un truc qui ne va pas non ?
#7 - 29-07-2013 13:23:09
- Nombrilist
- Expert de Prise2Tete
- Enigmes résolues : 10
- Messages : 568
amateurs de boules, eb mode hardcore !
On sait que l'on peut trouver l'intruse:
(1) parmi 13 boules en 3 pesées. (2) parmi 14 boules en 3 pesées si on détient une quinzième boule dont on sait qu'elle est bonne.
Pour 40 boules, on pèse d'abord 13 contre 13. Si égalité, alors on est dans le cas 2. Si non-égalité, alors on retire 7 boules de chaque côté. Si égalité, alors on est dans le cas 2. Si inégalité, alors il y a au plus 3 pesées à réaliser pour trouver l'intruse car on est alors dans le cas 1.
Donc, pour 40 boules, je trouve l'intruse en 5 pesées au maximum.
#8 - 29-07-2013 13:55:11
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 6,004E+3
amateurs de boules, en modz hardcore !
40 x 2 = 80 < 81= 3^4 : 4 pesées
121 x 2 = 242 <243 =3^5 : 5 pesées
Si 3^(n-1) < double du nombre de boules < 3^n : n pesées.
#9 - 29-07-2013 14:55:38
- kossi_tg
- Professionnel de Prise2Tete
- Enigmes résolues : 18
- Messages : 307
- Lieu: Montargis
Aateurs de boules, en mode hardcore !
Oui Titoufred, il y a un souci. Le problème vient de la formulation de la phrase. Ce n'est pas 10 boules de A et 10 boules de B1 sur chaque plateau
mais 10 boules de A sur un plateau et 10 boules de B1 sur l'autre plateau
. Merci, je vais rectifier ca dans ma réponse. Merci
#10 - 29-07-2013 20:10:18
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Amaters de boules, en mode hardcore !
@kossi_tg : bravo à toi, mais on peut faire moins de pesées.
@Nombrilist : bravo à toi, mais on peut faire moins de pesées.
@gwen : Pourquoi ?
#11 - 29-07-2013 21:24:34
- PRINCELEROI
- Elite de Prise2Tete
- Enigmes résolues : 33
- Messages : 1274
amateurs de boules, en mose hardcore !
Pour 40: 13 vs 13 et 14 de côté. si = j'ai 14 et une normale connue,je sais faire si si si [latex]\ne[/latex] 9+,4- vs 9n,4+ reste 9- j'ai soit 9+ soit 9- soit 4+4- pour 4+,4- 2+,1- vs 1-,2+ reste 2 - je détaille pas (tu l'as pas fait pour la mienne na!)
si j'avais 41et une normale à disposition je ferais 14 vs 13,1n et 14 restantes si= cas 14 +1,
si [latex]\ne[/latex] 9+,4- vs 5+,8n reste 9- si = cas 9 identiques si [latex]\ne[/latex] j'ai soit 9+ soit 5+ 4- si 5+,4- alors 3+,1- vs 2+,2n reste 3- j'obtiens 3+ ou 3- ou 2+1- cas déterminable en 1 pesée.
Donc pour 40 ou 41 avec 1 normale connue j'ai 4 pesées.
pour 121 je fais 40 vs 40 et 41 de côté.
pour le cas général Un=3U(n-1)+1
Je crois!
#12 - 29-07-2013 22:14:40
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 6,004E+3
Amateurs de boules,, en mode hardcore !
C'est pénible, j'ai l'impression de répéter la même chose sur 4 ou 5 sujets différents.
Il faut raisonner en base 3. G : penche à gauche D : penche à droite E : equilibre
Quelle que soit la situation, n pesées ne peuvent engendrer que 3^n cas de figure donc on a la limite basse. S'il y a 3^n +1 cas possibles, on ne peut pas conclure....
Le hic c'est qu'on ne sait pas si la boule est plus lourde ou plus légère... Donc tous les symétriques du genre EDD EGG ou DEG GED.... sont identiques. On reste donc sur les combinaisons telles que :
E= équilibre P = penche A = penche d'un autre côté
L'equilibre constant n'est qu'un cas. Pour les autres on divise par 2. =>( 3^n-1)/2
Le minimum nécessaire et le minimum suffisant sont donc égaux.
Pour rester simple : la première pesée déséquilibrée est déterminante. chaque série de pesées dont une au moins est déséquilibrée admet un exact symétrique qui ne sert à rien pour la conclusion, ça dépend juste du côté de la balance que je regarde. En gros , je garde toutes les séries de pesées dont la première déséquilibrée penche à gauche(quitte à y substituer le symétrique). Hormis le cas d'un équilibre à chaque fois, ça laisse la moitié des cas déterminants et déterminables.. D'où le (3^n )/2 +1.
#13 - 30-07-2013 01:03:20
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Amateurs de boules, en mod hardcore !
@Prince : Oui, bravo pour 40 boules ! Pour 121, tu peux détailler un peu stp ? Pour le cas général, j'imagine que tu parles du nombre max de boules parmi lesquels on peut déterminer une intruse en n pesées ? Aurais-tu un début de raisonnement ?
@gwen : 1) Dans ton raisonnement, tu cherches un nombre max de boules parmi lesquelles il serait possible de déterminer une intruse en n pesées c'est ça ? Et ce nombre serait 3^n/2 + 1 ? 2) Il va falloir également voir l'autre phase du raisonnement, c'est-à-dire prouver que c'est effectivement possible. 3) Tu ne veux pas d'abord montrer comment tu ferais pour 40 boules ? puis 121 ?
#14 - 30-07-2013 12:55:32
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 6,004E+3
Amateurs de boules, en mode hardocre !
Mais si, sauf que je l'azi fait pour 13 boules et 3 pesées dans un autre sujet.
Je vais faire un effort et détailler pour 40 mais pour 121 , il va falloir vous contenter de comprendre ma méthode... Il suffit de savir compter et associer des compléments en base 3. Pour une boule, on saura que c'est celle-ci mais il restera l'indétermination du sens de variation..
Avec un lien ce sera plus lisible peut-être : http://www.prise2tete.fr/upload/gwen27-40boules.PNG
#15 - 30-07-2013 13:51:33
- PRINCELEROI
- Elite de Prise2Tete
- Enigmes résolues : 33
- Messages : 1274
Amaterus de boules, en mode hardcore !
pour 121 boules
P1: 40 vs 40 reste 41
A) si = alors: j'ai 41 inconnues et une normale à disposition je fais 14 vs 13,1n et 14 restantes si= cas 14 +1 (cas pouvant être résolu en 3 pesées prédéfinies)
1,2,3,4,5 vs 6,7,8,9,C 2,3,7,8,12 vs 4,6,10,11,C 1,2,4,8,10 vs 3,5,11,13,C 0 pour équilibre. 1+ 101 1- 202 2+ 111 2- 222 3+ 112 3- 221 4+ 121 4- 212 5+ 102 5- 201 6+ 220 6- 110 7+ 210 7- 120 8+ 211 8- 122 9+ 200 9- 100 10+ 021 10- 012 11+ 022 11- 011 12+ 010 12- 020 13+ 002 13- 001 14 000
si [latex]\ne[/latex] 9+,4- vs 5+,8n reste 9- si = cas 9 identiques si [latex]\ne[/latex] j'ai soit 9+ soit 5+ 4- si 5+,4- alors 3+,1- vs 2+,2n reste 3- j'obtiens 3+ ou 3- ou 2+1- cas déterminable en 1 pesée. Soit 5 pesées en tout.
B)si [latex]\ne[/latex] P2: 13+ 27- vs 13- 27n reste 27+ s1 27x : 9x vs 9x puis 3x vs 3x et 1x vs1 x
si 13+ et 13- P3: 9+4- vs 9n4+ reste 9-
si 4+ 4- P4: 1-1+1n vs 2-1+ reste 2+1-
p5:si = 1+ vs 1+ si + 1+ vs 1+ si - 1- vs 1-
j'ai donc 5 pesées
cas général: Il faut 2 valeurs par boules et la balance donne 3 valeurs par pesées. En utilisant les boules connues on gagne une valeur donc 5 boules pour 2 pesées,14 boules pour 3 pesées etc
Si on a toujours une boule connue disponible on a pour n pesées 3^n + 1(valeurs)= 2x(boules)
#16 - 30-07-2013 14:11:44
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
mateurs de boules, en mode hardcore !
Ok gwen, j'avais déjà vu la solution pour 13 boules et 3 pesées, mais je n'avais pas compris l'algorithme général qui se cachait derrière. Le but de mon sujet est de réfléchir à une généralisation. J'ai vraiment du mal à comprendre ce qui se trame dans tes différents tableaux. Que sont les combinaisons primaires et associées dont tu parles ? En fait, tes pesées sont déterminées à l'avance quels que soient les résultats des précédentes ?
#17 - 30-07-2013 15:42:35
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 6,004E+3
Amateurs de boulees, en mode hardcore !
Oui, c'est plus simple. De toute façon, il y a 81 résultats de pesées possibles. On ne peut pas donner le symétrique d'une solution à une autre boule car suivant si elle est plus légère ou lourde, une boule prend deux solutions similaires ou les 1 et 2 s'inversent. Si je dis qu'une boule est liée à 1020, si elle est plus lourde elle fera pencher G=D= mais si elle est plus légère, elle fera pencher D=G= ! Donc je dois attribuer 2010 à la même boule, c'est ce que j'appelle combinaison associée. Si une autre boule répondait à 2010, il serait impossible de conclure entre les deux.
La première partie du tableau représente toutes les combinaisons commençant par 1 : 1 représente le sens ou la balance penche en premier. Dans les pesées suivantes, 1 représente un déséquilibre dans le même sens et 2 un déséquilibre dans l'autre sens. Les solutions symétriques peuvent tout simplement être traduites avec les même termes, elles sont équivalentes (à part droite ou gauche pour le premier déséquilibre) et elles s'excluent toutes les unes les autres.
Pour déterminer les pesées, il suffit donc de dire : 1, je met la boule à gauche, 2 à droite et 0 hors balance.
Donc, j'ai 40 boules et 81 solutions dont une est son propre symétrique (0000) On pourrait penser que ça permet de tester 41 boules mais on parle de puissances de 3, donc impaires. Le souci est que par principe ça fait donc un nombre impair de boules à poser à chaque pesée, donc il faut éliminer un des cas ou une boule est sur un plateau à chaque pesée. (quelle que soit la puissance de 3)
Par choix, je retire 1111, (et 2222 par conséquence) Mais on doit pouvoir en choisir une autre.
Je cherche ensuite une balance entre les solutions symétriques pour que chaque pesée soit faite avec le même nombre de boules de chaque côté. Pour parfaire cet algorithme sans "bidouiller" un peu à la fin, je ne sais pas...Peut-être une combinaison sur 2 avec le code gray, ça a l'air pas mal. Mias le but est d'obtenir sur chaque ligne de pesée autant de 2 que de 1 ce qui détermine des pesées sans réfléchir. Le résultat en base 3 des 4 pesées me donne le numéro de la boule.
Je mets juste en mémoire à chaque pesée 0, 1 ou 2 . Y'a pas plus simple comme mise en mémoire d'information
Le nombre de boules étant pair à chaque pesée
Si ça ne penche jamais c'est la 1(sans rien conclure sur elle) , si ça ne penche qu'à la troisième on sait si la 2 est plus lourde ou plus légère, si ça penche en deuxième c'est la 3, si ça penche dans le même sens aux 2 dernières pesées c'est la 4 , la 5 si les sens sont différents.... etc.
#18 - 31-07-2013 13:32:10
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Amateurs de boules, e nmode hardcore !
@Prince : Bravo pour le problème à 121 boules ! Pour le cas général, je ne demande qu'à te croire, mais il va falloir exposer quelques arguments.
@gwen : Ok, j'ai compris je crois ta méthode. C'est très ingénieux. Est-ce que ça peut marcher pour un nombre de boules n quelconque ? Il me semble par exemple que le fait que n soit de la forme 3x+1 est indispensable pour ta méthode (afin d'équilibrer le nombre de boules sur chaque plateau) non ?
#19 - 31-07-2013 13:45:35
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 6,004E+3
amareurs de boules, en mode hardcore !
Non, il suffit que le nombre soit pair à chaque pesée. Autrement dit je retire une pesée si le total est impair. S'il y a moins de boules, je garde moins de cas, ils s'excluent tous.
Avec 4 à 13 pesées : mettons 8 boules, je garde (par exemple mais on peut faire d'autres choix):
00001111 01110001 10120121
Ca donne : 000011 22 pour la ligne 1 011100 02 101201 12
Puis : 00 0 01122 01 2 10002 10 2 20112 pour les deux autres lignes avec effectivement un peu de "bidouillage, je ne trouve pas de recette pour cette étape...
Et les pesées :
5 6 / 7 8 2 4 /3 8 1 6 7 / 3 4 8
#20 - 31-07-2013 14:22:59
- PRINCELEROI
- Elite de Prise2Tete
- Enigmes résolues : 33
- Messages : 1274
Amateurs de obules, en mode hardcore !
Pour le cas général je précise:On peut trouver une boule de poids b parmi x boules dont x-1 sont de poids a que si: n le nombre de pesées x le nombre de boules x [latex] \leq \frac{3^n - 1}{2}[/latex] Chaque pesées donne 3 résultats possibles pour n pesées on a 3^n résultats. Chaque boule est soit normale soit intruse soit 2 possibilités. Pour n boules il faut 2n résultats pour déterminer le statut des n boules. Je ne comprends pas ce que tu veux comme démo. J'ai conscience de la légèreté de ma démo mais je bloque.
#21 - 03-08-2013 22:19:13
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
amateurs de bouleq, en mode hardcore !
PRINCELEROI a écrit:Je ne comprends pas ce que tu veux comme démo
Juste essayer de me convaincre que ce que tu fais avec 40 ou 121 boules, tu es capable de le faire avec un nombre n quelconque de boules.
#22 - 03-08-2013 23:19:59
- PRINCELEROI
- Elite de Prise2Tete
- Enigmes résolues : 33
- Messages : 1274
amatzurs de boules, en mode hardcore !
ok Pour 198562 boules je cherche n en fonction du nombre de boules à partir de ma formule.j'obtiens 88574 boules résolubles en 11 pesées avec une boule connue. je mets 54994 de chaque côté de la balance et mets 88574 boules de côté. et à chaque pesées je me réfère à la valeur de x en fonction de la valeur n précédente.
J'essaie de me retrouver dans une configuration connue.Exemple pour 121 (3x40 +1) je cherche à me retrouver avec 41 inconnues et une normale à disposition ou 40 + et 40- .
EDIT: Plus clairement: x les boules n le nombre de pesées
avec une connue on x=[(3^n)+1]/2 sans connue on a x=[(3^n)-1]/2 J'encadre mon nombre de boules avec une de chaque (les plus proches).
Pour tous x=[(3^n)-1]/2 il existe 1x' et 2x" tel que x'=[(3^(n-1))+1]/2 et x"=(x-1)/3 et x=x'+2x"
je compare les x" en gardant x' de côté.
#23 - 05-08-2013 13:49:49
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Amateurs de boules, en mode hardcorre !
Que fais-tu après si la première pesée est déséquilibrée ? Que fais-tu si le nombre de boules n'est pas de la forme E((3^n)-1)/2 ?
#24 - 07-08-2013 09:36:43
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3222
- Lieu: Luxembourg
amateurs de bouleq, en mode hardcore !
Voici un fichier intéressant trouvé sur la toile à ce sujet: http://archive.numdam.org/ARCHIVE/MSH/M … __29_0.pdf Je comprends pas vraiment pourquoi le fait de savoir que l'intruse est juste de poids différent (au lieu de savoir si elle est plus légère ou plus lourde) complique autant le problème. Ne s'en sortirait-on pas avec juste une pesée complémentaire ?
Edit: Après relecture de cet article, je comprends mieux maintenant: Le nombre minimum de pesées nécessaires pour déceler une boule différente parmi n boules (ce qui est le sujet de ce topic) est de: N1=ent[log(2n)/log(3)], la notation (ent) étant la partie entière. Par contre, si on sait que cette boule est plus légère (ou plus lourde), alors ce nombre passe à: N2=ent[log(n)/log(3)]. Et comme on a aussi: N1=ent[log(n)/log(3)+log(2)/log(3)], on en déduit que: N1=N2 si dec[log(n)/log(3)]<1-log(2)/log(3) (soit env. 0,37) et N1=N2+1 sinon, la notation (dec) étant la partie décimale.
#25 - 07-08-2013 11:25:42
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Amateurs de boules, en mode hadcore !
ok franky, merci pour le lien.
Mots clés des moteurs de recherche
|
|