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.

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

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

J'explicite un peu le message de Vasimolo :

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

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

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

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

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

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

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

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

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

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

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 )



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

Vasimolo