Dis donc titoufred, t'as reçu un stock de boules que t'essayes d'écouler? 

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).

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.

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

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!

@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 ?

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)

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

Pour 13 : 

00000111111111 9 boules par pesée, une à retirer
00111000111222
01012012012012

0000011111111 balance 8/0 => 4 à basculer 
0011100011122
0101201201201

je prends parmi ceux précédés de 0 et suivis de 1 ou 2

000001111 2222
001110001 2211 balance 6/2 => 2 à faire basculer
010120120 2102

je prends parmi ceux précédés de 0 et suivis de 1 ou 2
Là ça aide, ça garde l'équilibre de la ligne précédente.

000 00 11112222
001 22 00012211
010 21 01202102 balance 4/4 rien à changer

A chaque pesée 4 à gauche, 4 à droite...
 6  7  8  9 / 10 11 12 13
 3  9 12 13 /  4  5 10 11
 2  5  7 11 /  4  8 10 13

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.

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

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.

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 ?

ok franky, merci pour le lien.