Enigme Les Oompalas (généralisation) @ Prise2Tete

Klimrod · #1

Bonjour tout le monde,

Pour ceux qui prennent le sujet en route et qui veulent connaitre les caractéristiques de cette tribu mystérieuse que sont les Oompalas, c'est ici que ça se passe :
http://www.prise2tete.fr/forum/viewtopic.php?id=10794

Depuis notre première rencontre, la tribu a pris de l'expansion et a annexé les villages voisins. On les appelle maintenant les Oompalas-Icicémieuxetlàossi...
Et on y trouve des yeux de couleurs bleus (les Ooms), de couleur verte (les Palas), de couleur rouge (les Ici), de couleur violette (les Cémieux), etc...
En fait, aujourd'hui, on ne sait plus très bien combien il y a de couleurs. Disons petit n.

Et comme ces peuples sont bâtisseurs et qu'il faut bien assurer la descendance de chacun, ils ont pris la précaution de creuser autant de grottes qu'il y a de peuples, donc petit n grottes.

Et comme ces peuples savent conserver leur tradition, une fois par mois, à la Nouvelle Lune, lors de la "Grande Nuit de la Procréation", tous les Oompalas-Icicémieuxetlàossi se retrouvent dans leurs grottes respectives, avec interdiction de se mélanger entre peuples différents.

Sauriez-vous dire comment, sans aide extérieure, ils arrivent à se séparer ainsi chacun dans leur grotte respective, sans qu'aucune indication sur les yeux des uns et des autres ne soit échangée et sans que chacun puisse obtenir une quelconque information sur ses propres yeux ?

Bon amusement !
Klim.

golgot59 · #2

J'ai trouvé d'abord avec 3 tribus, c'est plus simple à imaginer :

Chacun doit d'ailleurs être bon en calcul...

Pour 3 tribus :

Un membre compte les yeux bleus, les yeux rouges qu'il multiplie par 2 et les yeux verts qu'il multiplie par 3.

Si le résultat est un multiple de 3, il fonce vers la grotte 1,
Si c'est un multiple de 3 (+1); alors il se dirige vers la grotte 2,
Si c'est un multiple de 3 (+2); alors il se dirige vers la grotte 3,

NB : "multiple de 3 (+1)" signifie multiple de 3 au résultat duquel on ajoute 1

En effet, si un observateur regardait la tribu toute entière, il compterait B+2V+3R tribains (qui signifie ici membre de la tribu)
Si le tributaire (le membre de la tribu quoi) a les yeux bleu, il trouvera N-1
S'il a les yeux vert il obtiendra N-2
S'ils sont rouge, il tombera sur N-3

Ces 3 nombres sont des entiers consécutifs, l'un est donc un multiple de 3, les deux autres de 3 (+1); et de 3 (+2) respectivement.

On peut aisément généraliser en faisant la somme des membres aux yeux de chaque couleur affectés des coefficients 1, 2, 3, ..., n.
Ensuite, il suffit de regarder si cette somme est multiple de n, de n (+1), de n (+2), ... de n (+n-1).

Klimrod · #3

Réponse absolument parfaite de Golgot !

golgot59 · #4

Merci, je vais rougir

FRiZMOUT · #5

Je tente ça :

Chaque villageois fait le calcul suivant :

[latex]\left(\sum_{i=1}^{n}(i-1)N_i\right) \bmod{n}[/latex] (avec [latex]N_i[/latex] le nombre de villageois de la [latex]i^e[/latex] couleur)

et va dans la grotte correspondante.

Klimrod · #6

Bravo FRiZ également.

A noter que Golgot pourrait simplifier un tout petit peu, mais c'est du chipotage, le principe est correct pour vous deux.

godisdead · #7

En commençant par la première couleur, les Oom comptent cette couleur et se séparent en deux groupes suivant la parité.
Le groupe mixte ainsi créé continue avec la deuxième couleur.
etc.

Klimrod · #8

@godisdead : ta solution est intéressante, mais ce n'était pas la mienne.
Dans ta solution, comment un individu sait-il qu'il doit arrêter de compter et que le processus a pris fin pour lui, mais pas pour les autres ? N'oublie pas qu'il ne doit recevoir aucune indication sur la couleur de ses propres yeux...

titoufred · #9

Ça y est j'ai trouvé !

Il y a [latex]n[/latex] tribus que l'on note [latex]T_0[/latex], [latex]T_1[/latex], ... ,[latex]T_{n-1}[/latex].

Chacun compte combien il voit d'individus des tribus [latex]T_1[/latex], ... [latex]T_{n-1}[/latex] et il obtient [latex]n-1[/latex] nombres [latex]x_1[/latex], ... ,[latex]x_{n-1}[/latex].

Puis il calcule [latex]X = \sum_{k=1}^{n-1}{k x_k}=x_1+2x_2+...+(n-1)x_{n-1}[/latex]

et enfin le reste [latex]\bar X[/latex] dans la division de [latex]X[/latex] par [latex]n[/latex]

Ce reste [latex]\bar X[/latex], compris entre [latex]0[/latex] et [latex]n-1[/latex], correspond à la grotte dans laquelle il doit se rendre.

Explication du pourquoi ça marche :

Si l'on note [latex]y_i[/latex] le nombre d'individus de la tribu [latex]T_i[/latex] et [latex]Y = \sum_{k=1}^{n-1}{k y_k}[/latex] alors

pour un individu de la tribu [latex]T_i[/latex], on a [latex]x_i = y_i-1[/latex] et [latex]x_k=y_k[/latex] pour [latex]k\neq i[/latex]

donc [latex]Y-X=i[/latex] et donc [latex]\bar X \equiv Y-i [n][/latex]

Ainsi pour deux individus de tribus différentes, les [latex]\bar X[/latex] sont différents et ils se rendront donc dans des grottes différentes.

CQFD.

Vasimolo · #10

Bonsoir Klim

En fait c'est assez simple , chacun va compter les villageois de chacune des n couleurs ou plus exactement leur parité . Par exemple un villageois comptant un nombre pair dans la couleur 1 et un nombre impair dans les couleurs 2,3 et 4 va noter 0111 . Supposons par exemple qu'il y ait un nombre pair de villageois de chaque couleur ( un étranger compterait 00...00 ) . Quand les villageois font faire leurs comptes chacun va trouver un seul 1 correspondant à sa couleur et il ira dans la grotte correspondant à cette couleur . Dans le cas général , chacun va ajouter toutes positions des 1 , le résultat obtenu modulo n donnera le numéro de la grotte ( le décalage par rapport à 00...00->0 étant le même pour chacun ) .

Par exemple celui qui compte :

0111->2+3+4=9->1[mod 4] va dans la grotte 1 .
1011->1+3+4=8->0[mod 4] va dans la grotte 0 .

Amusant

Vasimolo

golgot59 · #11

Oui, j'ai repensé à la simplification, effectivement on peut se passer de compter une des couleurs d'yeux, car le résultat ne change pas.

On choisi n-1 couleurs, et on affecte n-1 coefficients. On regarde ensuite la même chose : si cette somme est multiple de n, de n (+1), de n (+2), ... de n (+n-1).

Klimrod · #12

Excellente réponse de Titoufred, et variante très élégante de Vasimolo.
Bravo à vous deux !

SHTF47 · #13

http://clutchmag.s3.amazonaws .com/wp-content/uploads/2012/05/UndercolorsOfBenetton_SS10_01.jpg

C'est ma solution la meilleure évidemment, et de loin !

Klimrod · #14

@ SHTF : Gros gourmand !

Dans l'énoncé, on dit qu'il faut choisir. Sinon, tu t'exposes à récolter Spoiler : ça :

Klimrod · #15

Bravo à tous les participants !

Effectivement, le problème originel de Titoufred était généralisable à un nombre quelconque de couleur d'yeux et autant de grottes.
Je vous renvoie aux réponses et explications ci-dessus.

Bravo en particulier à Vasimolo qui a oeuvré en franc-tireur sur une solution originale, bien qu'à titre personnel, je préfère la simplicité de la solution de la majorité.
Klim.

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 13-11-2012 18:00:21

les oompamas (généralisation)

#0 Pub

#2 - 13-11-2012 18:20:35

Les Oompalas (généralisatiion)

#3 - 13-11-2012 18:32:21

Les Oompalas (généralisatin)

#4 - 13-11-2012 19:41:06

Les Oompaas (généralisation)

#5 - 13-11-2012 20:07:24

les oompalas (générzlisation)

#6 - 13-11-2012 20:46:54

Les Ooompalas (généralisation)

#7 - 13-11-2012 23:51:02

Les Oompalas (généralisatin)

#8 - 14-11-2012 00:00:41

leq oompalas (généralisation)

#9 - 14-11-2012 03:33:17

les oompzlas (généralisation)

#10 - 14-11-2012 06:28:00

Les Oompallas (généralisation)

#11 - 14-11-2012 08:44:54

les oompalas (généralisatuon)

#12 - 14-11-2012 09:15:33

Les Oompalas (généralisatoin)

#13 - 14-11-2012 15:36:05

Les Oompaals (généralisation)

#14 - 14-11-2012 16:02:09

les oompalas (générakisation)

#15 - 19-11-2012 09:53:25

Les Oomplaas (généralisation)

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums