 |
#26 - 18-11-2012 13:37:36
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
bêtes er piè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.
#27 - 18-11-2012 13:57:35
- snoopdala
- Amateur de Prise2Tete
- Enigmes résolues : 32
- Messages : 8
bêtes et oièges
Je croix avoir trouvé pour le 5*5 ; 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,432E+3
Bêets 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 Pigèes
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,432E+3
Bêtes t Pièges
Ta question est biaisée Mathias 
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 
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 poè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 
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 ett Pièges
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. 
#33 - 19-11-2012 21:15:49
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
bêted 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 : 5,432E+3
#35 - 21-11-2012 17:36:11
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
BBêtes 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...
Mots clés des moteurs de recherche
|
 |