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 : 1746

Bêtes et Piègges

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 te Pièges

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 : 4733

Bêtes et Piges

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 piègrs

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 : 4733

êtes et Pièges

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 oièges

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 : 1746

Bêtes et Piège

J'explicite un peu le message de Vasimolo :

*Si [latex]n[/latex] est un multiple de 3 : on peut voir que l'on peut caser [latex]\frac{n}3[/latex] bêtes par ligne, donc

[latex]\frac{n^2}3[/latex] bêtes dans le carré. Par conséquent il faut au minimum [latex]\frac{n^2}3[/latex] pièges.

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

*Si [latex]n\equiv 1 ~[3][/latex] : on peut voir que l'on peut caser [latex]\frac{n-1}3[/latex] bêtes par ligne horizontalement plus [latex]\frac{n-1}3[/latex] bêtes verticalement sur une colonne, donc [latex]\frac{n^2-1}3[/latex] bêtes dans le carré. Par conséquent il faut au minimum [latex]\frac{n^2-1}3[/latex] pièges.

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

(avec [latex]1+2\frac{n-1}3[/latex] lignes de [latex]\frac{n-1}3[/latex] pièges et [latex]\frac{n-1}3[/latex] lignes de [latex]\frac{n-1}3+1[/latex] pièges.)

*Si [latex]n\equiv2 ~[3][/latex] : on peut voir que l'on peut caser [latex]\frac{n-2}3[/latex] bêtes par ligne horizontalement plus [latex]2\frac{n-2}3[/latex] bêtes verticalement sur deux colonnes, donc [latex]\frac{n^2-4}3[/latex] bêtes dans le carré. Par conséquent il faut au minimum [latex]\frac{n^2-4}3[/latex] pièges. En posant les pièges en diagonales, on voit qu'il faut [latex]\frac{n^2-1}3[/latex] pièges

(avec [latex]1+\frac{n-2}3[/latex] lignes de [latex]\frac{n-2}3[/latex] pièges et [latex]2\frac{n-2}3+1[/latex] lignes de [latex]\frac{n+1}3[/latex] 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 : 1746

Bêttes et Pièges

Pour [latex]n \equiv 2 [3][/latex] (et [latex] n\neq 2[/latex]), on voit tout de même assez facilement que ce n'est pas

possible de faire moins de [latex]\frac{n^2-1}3[/latex] 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é [latex]n\neq 2[/latex] :

*Si [latex]n[/latex] est un multiple de 3, le nombre de pièges est [latex]\frac{n^2}3[/latex]

*Si [latex]n[/latex] n'est pas un multiple de 3, le nombre de pièges est [latex]\frac{n^2-1}3[/latex]

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

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

bêtes et piègeq

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 : 1746

Bêtees et Pièges

Pour [latex]n \equiv 2 [3][/latex] (et [latex] n\neq 2[/latex]), j'ai trouvé une démonstration plus simple.

On peut trouver le moyen de caser [latex]\frac{n^2-1}3[/latex] 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 à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

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
02-09-2008 Enigmes Logiques
P2T
Ah bah ouais mais bon! par mon-eureka
24-03-2012 Enigmes Logiques
09-02-2016 Enigmes Logiques
P2T
Tr1 tr1 II par Enelya!
21-10-2009 Enigmes Logiques
28-11-2008 Enigmes Logiques
07-12-2009 Enigmes Logiques
P2T
11-02-2011 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