Processing math: 100%
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
[+]

 #26 - 18-11-2012 13:37:36

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Bêtes et ièges

Pour le 5x5 : Passetemps, une bête peut se poser au milieu !

Pour le 8x8 : ok pour Gwen, elpafio, godisdead, Passetemps et Klim.

@nodgim : je n'ai pas eu le temps de regarder la généralisation. Je m'y penche.

#0 Pub

 #27 - 18-11-2012 13:57:35

snoopdala
Amateur de Prise2Tete
Enigmes résolues : 32
Messages : 8

Bêtes et Piègges

Je croix avoir trouvé pour le 5*5smile; mais je n'ai pas prouvé que je ne peux pas faire mieux.
On place des pièges en C1,C2,A3,B3,D3,E3,C4etC5.

 #28 - 18-11-2012 18:38:55

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,427E+3

Btêes et Pièges

Dans ce type de problèmes le plus difficile est de montrer qu'on a bien atteint le minimum de pièges nécessaires . Pour un carré dont le côté n vaut 0 ou 1 modulo 3 la réponse est clairement n²/3 ou (n²-1)/3 qui est le nombre de triminos qu'on peut poser sur le terrain . Le cas n=2 modulo 3 est le plus sensible car on ne peut pas y mettre plus de (n²-4)/3 triminos , il faut alors poser un piège de plus pour éviter un carré 3X3 avec moins de trois pièges .

Vasimolo

 #29 - 18-11-2012 20:46:35

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Bêtes et Piièges

Vasimolo a écrit:

la réponse est clairement n²/3 ou (n²-1)/3 qui est le nombre de triminos qu'on peut poser sur le terrain

Ca ne me semble pas si évident que ça. C'était mon premier raisonnement, mais je me suis vite rendu compte que "un bloc par trimino" n'est pas une condition nécessaire et suffisante. Quelle est ta méthode pour remédier à ça ?


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #30 - 18-11-2012 23:10:14

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,427E+3

bêtes et piègeq

Ta question est biaisée Mathias smile

Un simple coloriage montre que n²/3 ou (n²-1)/3 pièges suffisent à interdire l'intrusion d'un trimino . Après il faut voir pourquoi on ne peut pas faire mieux , un seul cas pose problème celui où n-2 est divisible par 3 smile

Vasimolo

 #31 - 19-11-2012 07:44:07

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

bêtes et piègrs

Je ne vois pas en quoi elle est biaisée, et je ne comprends toujours pas. Toi qui m'avais habitué à des réponses visuelles détaillées, tu me déçois big_smile

Tant pis, alors...


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #32 - 19-11-2012 20:23:55

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Bêtes e Pièges

J'explicite un peu le message de Vasimolo :

*Si n est un multiple de 3 : on peut voir que l'on peut caser n3 bêtes par ligne, donc

n23 bêtes dans le carré. Par conséquent il faut au minimum n23 pièges.

Réciproquement, en posant les pièges en diagonales, on voit que ce nombre suffit.

*Si n1 [3] : on peut voir que l'on peut caser n13 bêtes par ligne horizontalement plus n13 bêtes verticalement sur une colonne, donc n213 bêtes dans le carré. Par conséquent il faut au minimum n213 pièges.

Réciproquement, en posant les pièges en diagonales, on voit que ce nombre suffit

(avec 1+2n13 lignes de n13 pièges et n13 lignes de n13+1 pièges.)

*Si n2 [3] : on peut voir que l'on peut caser n23 bêtes par ligne horizontalement plus 2n23 bêtes verticalement sur deux colonnes, donc n243 bêtes dans le carré. Par conséquent il faut au minimum n243 pièges. En posant les pièges en diagonales, on voit qu'il faut n213 pièges

(avec 1+n23 lignes de n23 pièges et 2n23+1 lignes de n+13 pièges.)

Bah mince, ça fait un écart de 1 piège. sad

 #33 - 19-11-2012 21:15:49

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

bêtes er pièges

Pour n2[3] (et n2), on voit tout de même assez facilement que ce n'est pas

possible de faire moins de n213 pièges.

En effet, avec le "pavage" de bêtes donné dans mon message précédent, qui couvre tout le carré nxn, sauf un petit carré 2x2 :

...33300
...44400
...55512
...66612
...77712
...........

Si l'on ne met pas de piège dans le carré 2x2, on est obligé de mettre 2 pièges dans une bête :

33x00
44x00
xx5xx
66612
77712

CQFD !

Par conséquent, pour un carré de côté n2 :

*Si n est un multiple de 3, le nombre de pièges est n23

*Si n n'est pas un multiple de 3, le nombre de pièges est n213

 #34 - 19-11-2012 23:21:50

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,427E+3

Bêtes te Pièges

MthS-MlndN a écrit:

Je ne vois pas en quoi elle est biaisée, et je ne comprends toujours pas. Toi qui m'avais habitué à des réponses visuelles détaillées, tu me déçois big_smile

Je prends un moment pour joindre un dessin , pour le reste il faudra attendre (  j'ai vu que Titou a rédigé une réponse que je n'ai pas eu le temps de lire )

http://img843.imageshack.us/img843/66/echiquier5x5.jpg

Le coloriage donne immédiatement un terrain bloqué car chaque trimino occupe une case de chaque couleur si on mine toute les cases d'une couleur donnée on interdit tout dépôt de trimino . La seule question qui reste alors en suspend : peut-on le faire avec moins de pièges ? C'était mon problème et c'est pour ça que je ne comprenais pas ta question .

De toute façon il n'y a pas mort d'homme lollollol

Vasimolo

 #35 - 21-11-2012 17:36:11

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1749

Bêts et Pièges

Pour n2[3] (et n2), j'ai trouvé une démonstration plus simple.

On peut trouver le moyen de caser n213 bêtes de la façon suivante :

............
............
............
34555...
34666...
34078...
22278...
11178...

 

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 78 pommes et que vous en prenez 43, combien en avez-vous ?

Sujets similaires

Sujet Date Forum
P2T
Bêtes et Pièges (2) par titoufred
23-11-2012 Enigmes Logiques
P2T
Questions pièges!? par thedoums
01-02-2011 Enigmes Logiques
P2T
Portraits de sages par nipon
27-03-2008 Enigmes Logiques
P2T
Suite logique - Utopic par FRiZMOUT
15-01-2009 Enigmes Logiques
P2T
Incendie de forêt? par DonutJack
31-03-2009 Enigmes Logiques
P2T
Enigme Sudoku par chibisuke
16-03-2013 Enigmes Logiques
19-08-2012 Enigmes Logiques
28-06-2009 Enigmes Logiques
P2T
22-07-2012 Enigmes Logiques

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