|
#1 - 15-04-2014 19:32:00
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
Gâtea u75
Mon pâtissier prépare Pacques assidument.
Avant cuisson, il range habituellement ses carrés de chocolat de taille [latex]2\times 2[/latex] sur une grille [latex]20\times 20[/latex] . 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 : 5,986E+3
Gâteauu 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
Gtâeau 75
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,426E+3
âGteau 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 : 5,986E+3
gâreau 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,426E+3
Gâteeau 75
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âteeau 75
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,426E+3
gâteai 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 : 5,986E+3
gâteay 75
Oui
#10 - 15-04-2014 21:42:47
- cogito
- Expert de Prise2Tete
- Enigmes résolues : 48
- Messages : 593
Gâeau 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,426E+3
Gâteau 7
@Gwen : alors c'est ça
Vasimolo
#12 - 16-04-2014 00:02:23
- cogito
- Expert de Prise2Tete
- Enigmes résolues : 48
- Messages : 593
Gâtea u75
Il y a sûrement plus simple.
#13 - 16-04-2014 01:02:32
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Gâtteau 75
On montre par récurrence sur n qu'une grille de dimensions (3n+2)x(3m+2) avec m[latex]\leq [/latex]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[latex]\leq [/latex]n+1.
Si m [latex]\leq [/latex]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âteau 57
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 : 3221
- Lieu: Luxembourg
gâteay 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,426E+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,426E+3
Gteau 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 : 3802
gâtezu 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,426E+3
gâtzau 75
Je ne crois pas Nogim
Vasimolo
#21 - 19-04-2014 12:46:47
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,426E+3
fâteau 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
|
|