Inscription / Connexion Nouveau Sujet
Joute n°5 : Les posts du pénitencier
Bonjour à tous,
Je vous propose une énigme un peu plus relevée pour les vacances, puisque vous avez du temps pour cogiter. 
Au pénitencier de Math Island, spécialisé dans la détention de dangereux criminels, le directeur est confronté à de nombreux problèmes de sécurité lors de l'appel quotidien.
Chaque matin, les détenus et les gardiens se placent sur un grand quadrillage de 8 cases sur 8 (chacun sur une case et toutes les cases sont occupées).
Si un prisonnier n'a pas de gardien à côté de lui pour le surveiller, il peut agresser une des personnes placées à côté de lui. De même, si un gardien n'a pas un autre gardien à côté de lui pour le protéger, il peut se faire agresser par un prisonnier.
Etre placé à côté de quelqu'un signifie se trouver sur une des cases adjacentes à la sienne, c'est-à-dire ayant un côté en commun. Chaque prisonnier et chaque gardien doit donc avoir au moins un gardien à côté de lui (en diagonale, ça ne compte pas).
Il faut donc placer judicieusement un certain nombre de gardiens sur le quadrillage mais, par souci de rentabilité, on veut un maximum de prisonniers dans le pénitencier. Toutefois, le nombre total de détenus et de gardiens est forcément égal à 64.
Questions : combien faut-il de gardiens au minimum pour assurer la sécurité au cours de l'appel et où doivent-ils être placés ?
Pour faciliter la correction et pour que tout le monde soit sur un pied d'égalité, vous donnerez l'emplacement des gardiens exclusivement par leurs coordonnées sur le quadrillage.
Vous pouvez faire un dessin mais il ne sera pas pris en compte dans la correction !
Relisez bien votre réponse avant de la poster !
solution avec 20 gardiens:
(1,D)
(1,E)
(1,H)
(2,A)
(2,B)
(2,H)
(3,D)
(3,E)
(3,F)
(5,A)
(5,B)
(5,C)
(5,F)
(5,G)
(5,H)
(7,D)
(7,E)
(8,A)
(8,B)
(8,G)
(8,H)
Comme j'ai déjà perdu pour le mois, je réponds sans plus attendre...
Je trouve 20 gardiens au minimum...
Je les place en B1-C1, F1-G1, A3-A4, D3-E3, H3-H4,C5-C6,F5-F6, A7-A8, D8-E8,H7-H8.
Bonjour,
Voici ma proposition avec 20 gardiens :
A4 A7
B1 B2 B4 B7
C4
D6 D7 D8
E1 E2 E3
F5
G2 G5 G7 G8
H2 H5
Et ci après en image...
Merci pour l'énigme 
!
Bonjour,
Une solution avec 20 gardiens:
A1 A4 A5 A8 B1 B8 C3 C6 D3 D6
E1 E8 F1 F4 F5 F8 H2 H3 H6 H7
Une énigme comme on les aime !
Bonsoir, il faut un minimum de 20 gardiens placés en A4 A5 C4 C5 F4 F5 H4 H5 B1 B2 B7 B8 G1 G2 G7 G8 D2 D7 E2 E7.
merci pour l'énigme.
Salut godefroy_lehardi,
Je propose un minimum de 20 gardiens :
B1, G1, B2, D2, E2, G2, A4, C4, F4, H4, A5, C5, F5, H5, B7, D7, E7, G7, B8 et G8.
Alors je dirais au moins 20 gardiens sans grande conviction parce que je ne vois pas comment démontrer ce genre de problème. Voila ma réponse :
A2 ; B2 ; D1 ; E1 ; B4 ; B5 ; A7 ; B7 ; D3 ; E3 ; D6 ; E6 ; D8 ; E8 ; G2 ; H2 ; G4 ; G5 ; G7 ; H7
Merci pour cette énigme!
Bonsoir godefroy_lehardi
j'ai été pris par le chrono encore une fois car absent tout l'après-midi mais avant d'arriver à une solution optimale selon moi, il m'a quand même bien fallu 1 heure 
Ma proposition de positionnement pour les 20 gardiens est la suivante :
D1 ; E1 ; A2 ; B2 ; G2 ; H2 ; D3 ; E3 ; B4 ; G4 ; B5 ; G5 ; D6 ; E6 ; A7 ; B7 ; G7 ; H7 ; D8 ; E8
Merci pour cette énigme en espérant avoir eu raison de jouer sur la symétrie
J'ai trouvé une solution à gardiens positionnés sur les cases suivantes :
(A, 3), (A, 4), (A, 7), (A, 8),
(B, 1),
(C, 1), (C, 5), (C, 6),
(D, 3), (D, 8),
(E, 3), (E, 8),
(F, 1), (F, 5), (F, 6),
(G, 1), (H, 3),
(H, 4), (H, 7), (H, 8)
Bonjour,
après une recherche rapide puis une recherche un peu plus poussée (incitée par la formulation de l'énoncé et le nombre d'étoiles),
je pense qu'on ne peut faire moins de 20 gardiens.
(même si un léger doute subsiste...)
Voici une réponse en image:
Dommage qu'il faille ensuite les coordonnées :
A4-A5-B1-B2-B7-B8-C4-C5-D2-D7-E2-E7-F4-F5-G1-G2-G7-G8-H4-H5
J'ai choisi une solution symétrique mais il m'en reste d'autres à 20 (avec lignes de 3 ou 4 gardiens même).
Merci pour l'énigme.
Bonjour,
Je propose 20 gardiens placés comme suit
(B,1) (G,1)
(B,2) (D,2) (E,2) (G,2)
(A,4) (C,4) (F,4) (H,4)
(A,5) (C,5) (F,5) (H,5)
(B,7) (D,7) (E,7) (G,7)
(B,8) (G,8)
Bonsoir,
Je trouve une solution avec 20 gardiens placées ainsi :
(A,1) ; (A,2) ; (A,5) ; (A,6) ; (B,8) ; (C,3) ; (C,4) ; (C,8) ; (D,1) ; (D,6) ; (E,1) ; (E,4) ; (E,6) ; (F,4) ; (F,8) ; (G,2) ; (G,8) ; (H,2) ; (H,5) ; (H,6)
Dans ce genre d'énigme, le problème c'est toujours la minimalité. Même avec ordinateur on ne peut pas tester toutes les solutions (19 parmi 64 dépasse 10 puissance 15, tester tous les cas reste à la limite faisable jusqu'au milliard). Cependant je me suis bien cassé la tête et pas moyen de trouver une solution à 19 (encore moins à 18) et avec l'ordinateur cependant je peux montrer que en dessous de 16 (inclus) c'est impossible. Donc la solution est comprise entre 17 et 20. Et donc j'espère que ce sera 20.
Merci pour l'énigme !
Bonjour,
J'arrive à 23 gardiens et donc 41 prisonniers
placés en :
B1 E1 F1
B2 G2 H2
D3 E3
A4 B4 F4 H4
A5 F5 H5
C6 D6
E7 G7
A8 B8 E8 G8
20 gardes sont nécessaires :
B1 - E1 -
B2 - E2 - G2 - H2 -
E3 -
A4 - B4 - C4 -
F5 - G5- H5 -
D6 -
A7 - B7 - D7 - G7 -
D8 - G8
Au moins une autre solution symétrique existe. Merci pour l'énigme
Bonsoir,
quand il faut deux gardiens ensemble, on peut au maximum surveiller 6 prisonniers.
8 cases sont occupées. Cela veut dire que pour 64 cases on pourrait avoir au minimum 16 gardiens avec 48 prisonniers. En moyenne il y aurait 1 gardien pour
3 prisonniers.
Compte tenu du remplissage du damier, cette solution optimale n'est pas possible.
Je propose donc l'oeuvre d'art contemporaine ci-dessous qui montre que 20 gardiens surveillent 44 prisonniers. Le rapport est de 1gardien/2,2 prisonniers.
Bien à vous
Après une multitude de réponses avec 24 gardiens, j'ai enfin trouvé une solution avec 20, ce qui semble être le minimum.
voici les coordonées des 20 gardiens :
1B ; 1E ; 1F
2B ; 2H
3D ; 3H
4A ; 4D ; 4F
5A ; 5F
6C ; 6D ; 6H
7H
8A ; 8B ; 8E ; 8F
@++
en image cela donne :
avec un minimum de 28 gardiens :
A2-A3-A6-A7-B1-B4-B5-B8-C1-C8-D2-D3-D6-D7-E4-E5-F1-F7-F8-G1-G3-G6-H1-H2-H4-H5-H7-H8
Bonjour,
je pense qu'il y aura au moins 20 gardiens, si j'ai bien compris les gardiens doivent toujours être pas deux pour ne pas être agressés.
Voici donc ma proposition de réponses pour cette énigme:
Gardien en 1B, 1C, 1F et 1G.
En 3A, 3D, 3E et 3H.
En 4A, et 4H.
En 5C et 5F.
En 6C et 6F.
EN 7A et 7H.
Et enfin en 8A, 8D, 8E et 8H.
Voila, je suis pressée de connaitre la réponse.
Merci à tous
Il faut minimum 20 gardiens pour assurer la sécurité avec les contraintes du problème. Une façon possible de les placer est la suivante :
A4, A7, B1, B2, B4, B7, C4, D2, D6, D7, D8, E2, F4, F5, G1, G2, G7, G8, H4, H5
Pour la methode, j'ai simplement utiliser glpk (gnu linear programing package)
param n:=8;
param m:=8;
var place { 1..n, 1..m } binary;
minimize guards_number :
sum {i in 1..n, j in 1..m} place[i,j]
;
subject to security_constraint { i in 1..n, j in 1..m } :
(if i>1 then place[ i-1, j ])
+(if i<n then place[ i+1, j ])
+(if j>1 then place[ i , j-1 ])
+(if j<m then place[ i , j+1 ])
>= 1
;
solve;
printf "\n"; printf { i in 1..n } : "#"; printf "\n";
printf { i in 1..n, j in 1..m } :
(if place[i,j] then "G" else ".")
& (if j=m then "\n" else "")
;
printf { i in 1..n } : "#"; printf "\n"; printf "\n";
end;
qui nous donne une fois lancé.
>glpsol --model Joute_n°5.mod
Reading model section from Joute_n░5.mod...
24 lines were read
Generating guards_number...
Generating security_constraint...
Model has been successfully generated
ipp_basic_tech: 1 row(s) and 0 column(s) removed
ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced
ipp_basic_tech: 0 row(s) and 0 column(s) removed
ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
glp_intopt: presolved MIP has 64 rows, 64 columns, 224 non-zeros
glp_intopt: 64 integer columns, all of which are binary
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
Problem data seem to be well scaled
Crashing...
Size of triangular part = 64
Solving LP relaxation...
0: obj = 0.000000000e+000 infeas = 6.400e+001 (0)
* 90: obj = 2.400000000e+001 infeas = 0.000e+000 (0)
* 105: obj = 2.000000000e+001 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 105: mip = not found yet >= -inf (1; 0)
+ 125: >>>>> 2.000000000e+001 >= 2.000000000e+001 0.0% (6; 0)
+ 125: mip = 2.000000000e+001 >= tree is empty 0.0% (0; 11)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 0.1 secs
Memory used: 0.3 Mb (266633 bytes)
########
...G..G.
GG.G..G.
...G....
.G...GGG
.G......
...GG...
GG....GG
...GG...
########
Model has been successfully processed
Bonjour,
apres quelques essais, je n'ai pas reussi a faire mieux que 20 gardiens. Je sens qu'on peut faire mieux mais bon, je propose quand meme :
A2-A3-A6-A7
C1-C4-C5-C8
D1-D8
E3-E4-E5-E6
G1-G2-G7-G8
H4-H5
Merci pour l'enigme
Bonjour!
J'ai trouvé un minimum de 20 gardiens
Emplacements:
1) B-1
2) G-1
3) B-2
4) D-2
5) E-2
6) G-2
7) A-4
8) C-4
9) F-4
10) H-4
11) A-5
12) C-5
13) F-5
14) H-5
15) B-7
16) D-7
17) E-7
18) G-7
19) B-8
20) G-8
Bonne soirée
Bonjour,
Je dirais 20 gardiens minimum :
A4; A5; B1; B2; B7; B8; D3; D4; D5; D6; E1; E8; F1; F4; F5; F8; H2; H3; H6; H7.
Bonjour,
Je représente un gardien par O et un prisonnier par X.
Je pense que pour optimiser le nombre de prisonniers, il faut caser un maximum de configurations comme celle-ci dans la grille :
voici le mieux que j'ai pu trouver :
Coordonnées des gardiens :
D1 - E1 - H1
A2 - B2 - H2
F3
C4 - D4 - F4
A5 - H5
A6 - D6 - E6 - H6
B8 - C8 - F8 - G8
qui donne 20 gardiens et 44 prisonniers.
Merci pour l'énigme.
Clôture de l'énigme :
J'avais peut-être un peu surestimé la difficulté de cette énigme.
Il y a avait évidemment plusieurs solutions, par symétrie ou par rotations. Il y a aussi des solutions plus « optimales » en termes de sécurité puisque certains prisonniers peuvent être surveillés par plus d'un gardien.
Sinon, pour un carré n x n, on peut montrer que le nombre minimal de gardiens est égal à n(n+2)/4
En tout cas, félicitations à totti1000 pour sa nouvelle (et très belle) victoire ! 
Un très grand bravo au champion du mois.
Totti1000 a évité les nombreux pièges et géré très efficacement le chronomètre...
Chapeau.
bonjour,
comme mentionné dans la clôture de l'énigme, il existe en effet plusieurs solutions avec 20 gardiens.
cependant, je ne comprends pas pourquoi celle que j'avais proposée (le 22/10 à 14h50) a été refusée.
qu'est-ce qui ne convient pas dans cette disposition?
oops! au temps pour moi
il faut que j'apprenne à compter, d'abord...
merci d'oublier mon dernier post!
A l'attention de Monsieur Godefroy le Hardi,
Monsieur,
J'aimerais au nom de la corporation que j'ai la charge honorifique de représenter, attirer votre attention sur une solution que j'estime bien plus "optimale" selon nos propres critères, basés sur une expertise professionnelle éprouvée : elle consiste à placer très exactement huit gardiens dans chaque rangée, soit en tout un effectif de soixante quatre gardiens, ce qui correspond à un total de seize jeux de trente deux cartes.
Bien cordialement,
-- Le Président du Syndicat des Gardiens de Prisons
Bonsoir Godefroy,
Tout d'abord merci pour les énigmes originales que tu proposes.
Ensuite, j'aimerais savoir où l'on peut voir (ou tout du moins se faire une idée) de la démonstration de ce résultat :
"Sinon, pour un carré n x n, on peut montrer que le nombre minimal de gardiens est égal à n(n+2)/4"
Merci d'avance !
Bonjour Noflah,
Cette énigme m'est venue à la lecture d'une épreuve des olympiades de mathématiques il y a quelque temps mais je n'ai pas retenu la démonstration. Je me rappelle juste qu'on raisonnait sur les diagonales (dans un sens puis dans l'autre).
Désolé de ne pouvoir t'en dire plus. 
LeDino >> c'est pas bien de se moquer de braves gens qui passent leurs journées derrière les barreaux alors qu'ils n'ont rien fait de mal, et entourés de gens peu recommandables, en plus.
Avec un peu de retard .... Toutes mes félicitations à totti1000 qui confirme mois après mois son statut de "champion de l'île".
Chapeau bas . Qui pourra l'arrêter !!
Bonjour Nofutur2 et LeDino,
Merci pour ces félicitations.
Nofutur2 >>
Qui pourra l'arrêter
Euh... C'est très simple, une joute avec des canons !!!
LeDino >> Félicitations à toi aussi pour ce mois, car tu as aussi fait le sans-faute...
Nombre de participations : 0
0,00 %0,00 %
0Temps de réponse moyen : 112:17:29.
Annuler
connectez vous