Inscription / Connexion Nouveau Sujet
Niveau 3 *
Partager :

Joute n°5 : Les posts du pénitencier

Posté par
godefroy_lehardi Posteur d'énigmes
22-10-10 à 14:06

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

Joute n°5 : Les posts du pénitencier

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 !

Joute n°5 : Les posts du pénitencier

Posté par
ksad
re : Joute n°5 : Les posts du pénitencier 22-10-10 à 14:50

perdusolution 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)

Posté par
Nofutur2
re : Joute n°5 : Les posts du pénitencier 22-10-10 à 15:30

gagné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.

Posté par
LeDino
Bonjour 22-10-10 à 16:00

gagné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

Posté par
gloubi
re : Joute n°5 : Les posts du pénitencier 22-10-10 à 16:11

gagné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

Joute n°5 : Les posts du pénitencier

Une énigme comme on les aime !  

Posté par
tomtess
re : Joute n°5 : Les posts du pénitencier 22-10-10 à 17:28

gagnéBonjour. Je propose 20 gardiens :
A2 A7 B2 B4 B5 B7 D1 D3 D6 D8 E1 E3 E6 E8 G2 G4 G5 G7 H2 H7
Merci

Posté par
Mello
re : Joute n°5 : Les posts du pénitencier 22-10-10 à 18:08

gagné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.

Posté par
totti1000
re : Joute n°5 : Les posts du pénitencier 22-10-10 à 18:49

gagné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.

Posté par
Nath000
Ma réponse 22-10-10 à 20:51

gagné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!

Posté par
Rodolphe
re : Joute n°5 : Les posts du pénitencier 22-10-10 à 23:00

gagné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

Posté par
franz
re : Joute n°5 : Les posts du pénitencier 23-10-10 à 08:56

gagnéJ'ai trouvé une solution à 4$\red 20 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)

Posté par
manpower
re : Joute n°5 : Les posts du pénitencier 23-10-10 à 13:19

gagné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:
Joute n°5 : Les posts du pénitencier

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.

Posté par
mathisgood
Prison break 23-10-10 à 15:33

gagné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)

Posté par
Noflah
re : Joute n°5 : Les posts du pénitencier 23-10-10 à 18:26

gagné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 !

Posté par
dpi
re : Joute n°5 : Les posts du pénitencier 23-10-10 à 18:53

perduBonjour,
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

Posté par
Nyavlys
re : Joute n°5 : Les posts du pénitencier 24-10-10 à 11:54

gagné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

Posté par
dpi
re : Joute n°5 : Les posts du pénitencier 24-10-10 à 16:00

perduRebonjour
Entre temps j'ai trouvé 21 /43
mais hors course

Posté par
castoriginal
Joute n°5 : Les posts du pénitencier 24-10-10 à 18:54

gagné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.

Joute n°5 : Les posts du pénitencier

Bien à vous

Posté par
carpissimo
re : Joute n°5 : Les posts du pénitencier 28-10-10 à 11:37

gagné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 :

Joute n°5 : Les posts du pénitencier

Posté par
alexia77
re : Joute n°5 : Les posts du pénitencier 29-10-10 à 11:02

perdu700

Posté par
CLARASATISH
re : Joute n°5 : Les posts du pénitencier 29-10-10 à 14:01

perduBonjour,


Il faut au minimum 32 gardiens.

Et ils doivent se placer entre deux détenues.

Posté par
loepower
re : Joute n°5 : Les posts du pénitencier 30-10-10 à 20:22

perduavec 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

Posté par
LCMD
réponse supposée 01-11-10 à 18:13

gagné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

Posté par
buzard
re : Joute n°5 : Les posts du pénitencier 01-11-10 à 21:34

gagné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)

Citation :

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

Citation :

>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

Posté par
cohlar
re : Joute n°5 : Les posts du pénitencier 02-11-10 à 11:16

gagné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

Joute n°5 : Les posts du pénitencier

Posté par
pulplette
re : Joute n°5 : Les posts du pénitencier 06-11-10 à 09:07

gagné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

Posté par
Ptit-Louis
re : Joute n°5 : Les posts du pénitencier 08-11-10 à 21:04

gagné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.

Posté par
lo5707
re : Joute n°5 : Les posts du pénitencier 10-11-10 à 19:18

gagné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 :
Joute n°5 : Les posts du pénitencier

voici le mieux que j'ai pu trouver :
Joute n°5 : Les posts du pénitencier

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.

Posté par
godefroy_lehardi Posteur d'énigmes
re : Joute n°5 : Les posts du pénitencier 13-11-10 à 13:25

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 !

Posté par
LeDino
Bravo 15-11-10 à 15:34

gagné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.

Posté par
ksad
re : Joute n°5 : Les posts du pénitencier 15-11-10 à 16:26

perdubonjour,
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?

Joute n°5 : Les posts du pénitencier

Posté par
ksad
re : Joute n°5 : Les posts du pénitencier 15-11-10 à 16:30

perduoops! au temps pour moi
il faut que j'apprenne à compter, d'abord...
merci d'oublier mon dernier post!

Posté par
godefroy_lehardi Posteur d'énigmes
re : Joute n°5 : Les posts du pénitencier 15-11-10 à 16:30

Bonjour ksad,

Vraiment désolé mais il y a 21 gardiens dans ta proposition.

Posté par
LeDino
Une solution optimale 15-11-10 à 19:53

gagné
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

Posté par
Noflah
re : Joute n°5 : Les posts du pénitencier 15-11-10 à 21:41

gagné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 !

Posté par
godefroy_lehardi Posteur d'énigmes
re : Joute n°5 : Les posts du pénitencier 16-11-10 à 07:19

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.

Posté par
Nofutur2
re : Joute n°5 : Les posts du pénitencier 24-11-10 à 10:32

gagné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 !!

Posté par
totti1000
re : Joute n°5 : Les posts du pénitencier 27-11-10 à 14:21

gagnéBonjour Nofutur2 et LeDino,

Merci pour ces félicitations.

Nofutur2 >>

Citation :
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...

Posté par
racincar
re : Joute n°5 : Les posts du pénitencier 22-12-10 à 20:53

il faut 20 gardien au minimum

Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 112:17:29.
Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !