Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 08-10-2011 22:06:41

Azdod
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 763
Lieu: In this universe ... !!

Les 12 peinters !

Douze peintres vivent dans douze maisons d'une même rue circulaire, peintes certaines en bleues et les autres en blanc.
Chaque fin de mois, l'un des peintres quitte sa maison avec ses pots de peintures et repeint chaque maison de la couleur contraire, en commençant par la sienne et dans l'ordre des aiguilles d'une montre.
Il s'arrête dès qu'il a repeint une maison blanche en bleu. Durant une année, un peintre donné ne fait cela qu'une seule fois.
Prouver que, si au début de l'année l'une au moins des maisons était peinte en bleu, alors à la fin de l'année chacune retrouvera sa couleur initiale !

Bonne chance



Annonces sponsorisées :

"Zero is where everything starts ! Nothing would ever be born if we didn't depart from there"
  • |
  • Répondre

#0 Pub

 #2 - 09-10-2011 01:32:58

MOSTZ
Habitué de Prise2Tete
Enigmes résolues : 33
Messages : 16

Les 12 peintrse !

Bonsoir,
merci pour cette belle enigme

désolé mon explication n'est pas écrite en langage mathématique ni en français, plutôt un mix des 2, comme ça sort smile
sur papier je me debrouille mieux lol mais au moins je vous donne "l'idée"

12 maisons bleues ou blanches    => on modelise ça en binaire par 12 chiffres 0 ou 1, 0 pour blanc, 1 pour bleu
par convention, on va les classer en commençant par le 0 jusqu'à 11 en faisant en sorte d'avoir la plus longue serie de maisons blanches debutant en 11eme rang (11eme, 1àeme etc)
notre nombre de 12 chiffres commencera par des 0 sauf si nombre = 111111111111

quant le peintre dépasse la 11ème maison, il passe à la 0ème puis à la 1ère etc par ordre croissant

en fait si on comprend bien, chaque peintre "sélectionné pour une tournée" va peindre les maisons consécutives en blanc si elles étaient bleues, sinon il s'arrete des qu'il en a croisé une blanche, apres l'avoir "bleutée".

Concernant notre nombre de 12 digits ecrits en base 2, c'est comme si on disait: à chaque rang (pour peintre selectionné) on retranche à notre nombre 2^ce rang et 2^ce rang +1 et ainsi de suite jusqu'à ce que l'on trouve un digit=0, et dans ce cas, on lui ajoute 1 (ce qui revient à ajouter 2^le rang supérieur du dernier atteint)

en résumé, si n= rang selectionné, à chaque fois cela revient ajouter:
      {-2^n - 2^(n+1) - ... - 2^(n+i)} + 2^(n+i+1)
=  -{(2^(n+i+1)-1)  -   (2^n -1)}      + 2^(n+i+1)
=   2^n
soit à ajouter 2^(le rang du digit de 0 à 11) à notre nombre.

pouvez tester sur des exemples...

PARTICULARITE:
Cependant, quand notre nombre est 111111111111 en base 12, soit 2^12-1, cad toutes les maisons sont bleues, le peintre va toutes les mettre en blanc puis remettre celle d'où il est parti en bleu, cela revient à retrancher 2^0+2^1+...+2^11 puis à y ajouter 2^rang du digit initial, soit au final à ajouter:   -(2^12-1)+2^n, soit comme avant avec un -(2^12 -1 ) en plus


**l'explication est un peu incomplete car il y a le cas où le peintre va depasser la 11è maison sans qu'il y ait nombre = 111111111111, il commence à se faire tard...


vu que les 12 peintres y passent, au final notre nombre va augmenter de 2^0 + ... +2^11, et il diminuera forcement de (2^12-1) vu que l'on aura forcement nombre=111111111111 en binaire a un moment donné en ayant au depart une maison bleue.

donc au terme des 12 mois, x => x + (2^12 -1 ) - (2^12 - 1) = x
pas très formel tout ça, mais ya plus qu'à, tout y est je pense sauf **

 #3 - 09-10-2011 04:37:30

Yuka2
Habitué de Prise2Tete
Enigmes résolues : 48
Messages : 31

Les 12 peiintres !

Je dis peut être une grosse bêtise mais il me semble que ce problème est généralisable avec N maisons, N peintres et N mois. on peut réinterpréter le problème de la sorte.

Si on code le problème en binaire tel qu'une maison bleue = 1 et une maison blanche = 0

On attribue le numéro 0 à une des maisons et on incrémente dans le sens des aiguilles d'une montre jusqu'à N-1.
Le code initial des couleurs des maisons de la rue est un nombre binaire codée sur N caractères. Appelons le A. (Le premier chiffre correspond à la couleur de la dernière maison et le dernier à celui de la première)

Il suffit de voir que lorsque le peintre de la maison X sort de chez lui, le nouveau code couleur des maisons correspond à :
A+2^X         si A+2^X < 2^N
A+2^X mod[2^(N)-1]      sinon

On ne sait pas l'ordre dans lequel les peintres vont sortir de chez eux mais par chance, l'addition étant associative et commutative, une fois que les N peintres seront sortis de chez eux le code couleur des maisons sera

     A + 2^0+ 2^1 + 2^2 + .... + 2^(N-1) si le résultat est < 2^N
     A + 2^0+ 2^1 + 2^2 + .... + 2^(N-1)  mod[2^N -1] sinon

C'est à dire :
     A + 2^N - 1 si le résultat est < 2^N
     A + 2^N - 1 mod[2^N - 1] sinon

Autrement dit :
     2^N - 1 si A = 0
     A sinon

ce qui signifie qu'on obtient que des maisons bleues s'il n'y avait que des maisons blanches initialement (A=0) ou alors on retombe le résultat initial si A>0 ie s'il y avait au moins une maison bleue.

L'avantage de cette méthode c'est qu'elle marche pour tout N et pas seulement N=12 et qu'on peut trouver l'état des maisons très facilement pour toute sous partie de peintres étant déjà sortis de chez eux

Au passage, très belle énigme !!

Bon c'est peut être un peu indigeste ci dessus donc je le refais avec un exemple.Spoiler : [Afficher le message]
Imaginons qu'on ait 5 maisons
             0 Bleue

4 Blanche            1 Blanche

   3 Blanche       2  Bleue

On code la rue initiale en binaire.
Dans cet exemple on a donc A = 00101 = 0*2^4 + 0*2^3 + 1*2^2 + 0*2^1 + 1*2^0

1) Quand un peintre d'une maison blanche sort de chez lui, il ne fait que rendre sa maison bleue. Par exemple celui de la maison 4 :
             0 Bleue

4 Bleue           1 Blanche

   3 Blanche       2  Bleue

Le nouveau code est 10101 = 00101 + 10000 = A + 2^4 =A1

2) Quand un peintre d'une maison bleue sort de chez lui, il rend sa maison blanche et continue jusqu'à ce qu'il rencontre une maison blanche.
Par exemple celui de la maison 2 qui va inverser les couleurs des maisons 2 et 3
                      0 Bleue

4 Bleue                  1 Blanche

            3 Bleue    2  Blanche

Le nouveau code est 11001 = 10101 + 00100 = A1 + 2^2 = A2

Et ainsi de suite ...

Le coup du modulo ne sert qu'à revenir à la première maison si un peintre peint la dernière maison de bleue à blanc.
comme c'est le cas ici si le peintre 3 sort de chez lui à la 3ème étape.

                 0 Blanche

4 Blanche                    1 Bleue

   3 Blanche  2  Blanche

Le code devient 00010 = 11001 + 01000 mod(11111)= 100001 mod (11111) = 11111 + 00001 + 00001 mod (11111) = 00010 = A2 + 2^3 mod(2^5 -1)

 #4 - 09-10-2011 20:56:30

MOSTZ
Habitué de Prise2Tete
Enigmes résolues : 33
Messages : 16

Les 12 peinres !

Bonsoir Azdod,
suis-je à côté de la plaque ou c'est à peu près ça (à creuser + à formaliser)?

Merci
Sinon j'ai adoré y passer un moment

 #5 - 10-10-2011 03:32:00

Azdod
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 763
Lieu: In this universe ... !!

les 12 peontres !

2 Bonnes réponses


"Zero is where everything starts ! Nothing would ever be born if we didn't depart from there"

 #6 - 15-10-2011 03:19:43

Azdod
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 763
Lieu: In this universe ... !!

Lse 12 peintres !

Seulement 2 réponses ! Réveillez vous les logiciens de P2T big_smile!

Spoiler : indice Utiliser l'écriture en binaire


"Zero is where everything starts ! Nothing would ever be born if we didn't depart from there"

 #7 - 15-10-2011 10:13:40

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

LLes 12 peintres !

Difficile de formaliser ce pb en langage mathématique...

Scénario pour chaque maison prise isolément:

1) 2 changements de couleur, dont 1 par le propriétaire et un autre par un voisin.
2) un et un seul départ vers la maison avale, soit du propriétaire, soit d'un voisin amont.
3) une et une seule arrivée d'un voisin amont.

Pour le 1)
Par le proprio, et si on suppose qu'il y a une arrivée amont, par ce voisin amont.

Pour le 2)
Si maison bleue quand proprio sort, c'est lui qui va vers l'aval et bloque le voisin amont qui s'arrêtera là. Si maison blanche, il rentre chez lui, non sans avoir peint sa maison en bleu, et donc autorise le voisin amont à continuer son chemin tout en peignant sa maison en blanc.

Pour le 3)
Si le proprio de la maison amont a une maison bleue, il pourra aller vers l'aval. Sinon il reste chez lui mais en autorisant le passage d'un autre voisin amont. De proche en proche, il n'y a que le cas où ttes les maisons sont blanches au départ qu'il n'y aura pas de déplacements et que ttes les maisons deviendront bleues. Mais ce cas a été exclu dans l'énoncé.

Le scénario proposé atteste donc que les couleurs initiales des maisons sont conservées après sortie de tous les peintres.

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Tim, Tam et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete