 |
#1 - 15-04-2014 19:32:00
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,433E+3
Gââteau 75
Mon pâtissier prépare Pacques assidument.
Avant cuisson, il range habituellement ses carrés de chocolat de taille 2×2 sur une grille 20×20 . Les sommets des carrés sont placés aux nœuds de la grille , les carrés peuvent être en contact mais ne se chevauchent jamais . Il a confectionné 48 carrés qu’il s’apprête à disposer sur la grille quand je lui propose d’ajouter un des miens . Comme il apprécie modérément mes dons culinaires ( et qu’il n’est pas toujours bon camarade ) il me dit qu’il doit d’abord disposer les siens et voir s’il reste une place .
Comment va-t-il faire pour m’empêcher de poser mon carré , si possible ?
Un exemple sur une grille 8x8 qui empêche la pose d’un 10ème carré .

Amusez-vous bien 
Vasimolo
#2 - 15-04-2014 19:43:23
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 6,037E+3
GGâteau 75
Comme ça dans une grille n x m avec ent [ (n+1)/3 ] x ent [ (m+1)/3 ] carrés.

#3 - 15-04-2014 20:51:54
- cogito
- Expert de Prise2Tete
- Enigmes résolues : 48
- Messages : 593
Gâteau 775
Bonsoir,
Au départ je me suis dit : "Non, il ne pourra jamais empêcher Vasimolo de rajouter son carré de chocolat."
Après je me suis rappelé : "C'est vrai qu'il est malin le bougre." Ce n'est pas très sympa de sa part :

En même temps, il faut dire que ce qu'il fait est très joli 
Il y a sûrement plus simple.
#4 - 15-04-2014 21:23:07
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,433E+3
Gâteauu 75
Je ne comprends rien aux deux réponses précédentes . La question n'est peut-être pas claire ?
Vasimolo
#5 - 15-04-2014 21:27:17
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 6,037E+3
gâteai 75
C'est un cas général pour ma part...
Sur une grille 20x20 il peut s'il a 49 carrés en main.
#6 - 15-04-2014 21:32:52
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,433E+3
Gâteau 5
Ta réponse n'est pas claire Gwen , le nombre que tu donnes est le nombre de carrés nécessaire pour bloquer la grille ?
Vasimolo
#7 - 15-04-2014 21:34:56
- cogito
- Expert de Prise2Tete
- Enigmes résolues : 48
- Messages : 593
Gâteau 5
Le dessin représente la grille 20*20. Les cases marrons correspondent aux carrées de chocolats (Les carrés 4*4 sont 4 carré 2*2 côte à côte) il a donc poser 48 carrée 2*2 (il y en a 4 isolés dans chaque coins) et il n'y a pas la place pour un 49ème. c'était bien cela qui était demandé ? J'aurais peut-être dû marquer les séparations entre deux carrés juxtaposés 
Il y a sûrement plus simple.
#8 - 15-04-2014 21:38:30
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,433E+3
Gâeau 75
@Cogito : il me semble que tu as posé bien plus de 48 carrés 2X2 , non ?
Vasimolo
#9 - 15-04-2014 21:39:28
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 6,037E+3
Gâteau 7
Oui 
#10 - 15-04-2014 21:42:47
- cogito
- Expert de Prise2Tete
- Enigmes résolues : 48
- Messages : 593
Gâtea 75
huhum... oui effectivement, dans ma tête je me suis dis il y en a 4 * 16 et 4 * 16 ça fait 48 c'est bien connu ! 
Bon pardon, j'y retourne 
Il y a sûrement plus simple.
#11 - 15-04-2014 21:46:34
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,433E+3
gâteai 75
@Gwen : alors c'est ça 
Vasimolo
#12 - 16-04-2014 00:02:23
- cogito
- Expert de Prise2Tete
- Enigmes résolues : 48
- Messages : 593
Gâteau 5
Il y a sûrement plus simple.
#13 - 16-04-2014 01:02:32
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
GGâteau 75
On montre par récurrence sur n qu'une grille de dimensions (3n+2)x(3m+2) avec m≤n nécessite au moins (n+1)x(m+1) carrés pour être bloquée.
Initialisation : Pour n=0, donc m=0, on a une grille 2x2 qui nécessite 1 carré pour être bloquée.
Hérédité : On suppose que c'est vrai pour un certain n et on se donne une grille de (3n+5)x(3m+2) avec m≤n+1.
Si m ≤n (grille non carrée), alors on coupe la grille en 2 grilles séparées d'une case (3n+2)x(3m+2) et 2x(3m+2) qui nécessitent chacune respectivement au moins (n+1)x(m+1) et (m+1) carrés soit au total (n+2)x(m+1) carrés. Le fait que les grilles soient séparées fait que les carrés de l'une ne peuvent aider à bloquer l'autre.
Si m=n+1 (grille carrée), alors on coupe en 4 grilles séparées d'une case : (3n+2)x(3n+2), 2x(3n+2), (3n+2)x2 et 2x2 qui nécessitent chacune respectivement au moins (n+1)x(n+1), (n+1), (n+1) et 1 carrés soit au total (n+2)x(n+2)=(n+2)x(m+1) carrés. Ce qui prouve l'hérédité.
#14 - 16-04-2014 10:27:01
- dylasse
- Professionnel de Prise2Tete
- Enigmes résolues : 21
- Messages : 378
Gâteeau 75
Notre bon pâtissier ne pourra pas t'empêcher de placer ton chocolat. Et tu le sais puisque tu as colorié (dans ta tête) 49 blocs 2x2 sur la plaque. Ces 49 blocs présentent la particularité qu'aucun chocolat 2x2 ne peut en recouvrir simultanément 2, donc après que ton pâtissier aura déposé ses 48 chocolats, un bloc de 4 sera libre pour le tien.

#15 - 16-04-2014 15:54:47
- Franky1103
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 3230
- Lieu: Luxembourg
Gâetau 75
Quand la grille carrée est du type 3n-2 < N =< 3n+1, en disposant n² carrés, on y arrive très facilement. Dans notre cas, il faudrait 49 (> 48) carrés. Il y a une astuce consistant à décaler les carrés, qui permet d'en économiser un, mais que je n'ai pas (encore) découverte. Affaire à suivre ...
#16 - 16-04-2014 17:38:47
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,433E+3
#17 - 17-04-2014 13:45:47
- nobodydy
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1677
#18 - 17-04-2014 18:00:11
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,433E+3
gâteai 75
@Nobodydy : ton intuition est bonne . Il y a des solutions très courtes , ce qui ne veut pas dire qu'elles sont faciles à trouver 
Vasimolo
#19 - 18-04-2014 07:19:24
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3814
Gâteua 75
Salut Vasimolo, En remplissant le casier comme un livre d'écriture, de gauche à droite et de haut en bas, en optimisant les espaces libres (1 unité systématique) on finit en bas en droite avec une agglomération de carrés sans espace libre. En ôtant le carré du coin, et en replaçant les carrés du pourtour on gagne ce vide.
#20 - 18-04-2014 08:54:03
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,433E+3
Gâteau 7
Je ne crois pas Nogim 
Vasimolo
#21 - 19-04-2014 12:46:47
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,433E+3
Gâteaau 75
J'avais une solution en numérotant les lignes de 0 à 20 et en remarquant que chaque ligne 1 ; 4 ; 7 ; 10; 13 ; 16 ; 19 devait rencontrer 7 gâteaux pour bloquer le jeu . Je préfère 100 fois celle de Dylasse qui démontre tout avec l'air de ne pas y toucher 
Merci à tous pour la participation .
Vasimolo
Mots clés des moteurs de recherche
|
 |