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 [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.

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