Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 15-04-2014 19:32:00

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4934

gâreau 75

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

http://img845.imageshack.us/img845/3319/eypq.jpg

Amusez-vous bien smile

Vasimolo



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 15-04-2014 19:43:23

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,679E+3

gâtrau 75

Comme ça dans une grille n x m avec ent [ (n+1)/3 ]  x  ent [ (m+1)/3 ] carrés.

http://www.prise2tete.fr/upload/gwen27-g75.JPG

 #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 :

http://www.prise2tete.fr/upload/cogito-gateau75.png


En même temps, il faut dire que ce qu'il fait est très joli lol


Il y a sûrement plus simple.

 #4 - 15-04-2014 21:23:07

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4934

Gâtea u75

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,679E+3

Gâteau 755

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 : 4934

Gâteau 755

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 57

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 hmm


Il y a sûrement plus simple.

 #8 - 15-04-2014 21:38:30

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4934

Gâteau 775

@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,679E+3

gâreau 75

Oui smile

 #10 - 15-04-2014 21:42:47

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

Gâetau 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 ! lol

Bon pardon, j'y retourne big_smile


Il y a sûrement plus simple.

 #11 - 15-04-2014 21:46:34

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4934

gâyeau 75

@Gwen : alors c'est ça smile

Vasimolo

 #12 - 16-04-2014 00:02:23

cogito
Expert de Prise2Tete
Enigmes résolues : 48
Messages : 593

âGteau 75

Bonne nouvelle !

Tu pourras rajouter ton carré de chocolat ! cool

http://www.prise2tete.fr/upload/cogito-Gateau75.png


Explication de texte dessin :

Dans une bande 20 * 4 (comme la colonne A) il sera toujours possible de mettre 7 carrés. Si on veut minimiser le nombre maximal de carrés que l'on peut mettre dans une bande 20 * 4, il faut que les carrés soient centrés (i.e. ne touche pas les bord de la bande sinon on pourrait mettre au même niveau un carré supplémentaire (puisque 4 = 2 * 2)).

Maintenant si on duplique la colonne A (qui contient le nombre de carré optimal)
pour optimiser le nombre de carrés dans une bande de largeurs 8, on s'aperçoit que les deux "bord" vide mis côte à côte créés un nouvel espace (en jaune) où nous pourrons toujours mettre 7 carrés. Si on décide de décaler un des 14 carrés
pour prendre la place d'un carré sur la bande jaune, alors d'après la dernière remarque du paragraphe précédent on aura créé la place pour un autre carré, donc le nombre de carrés total ne changerait pas. Tous ça pour dire que dans une bande de 20 * 8 on pourra toujours mettre 21 carrés.
(on ne pourra jamais en déplacer un pour prendre la place de 2 (ou alors si c'est le cas c'est qu'il est possible de mettre au moins huit carrés dans la colonne jaune donc au final, ça revient au même). Ce point de la démonstration est laissé en exercice pour le lecteur tongue)

Donc dans une bande de 20 * 16 on pourra toujours mettre 42 carrés.
(on n'a pas ce "phénomène de la bande jaune" ici. Ce point est aussi laissé en exercice pour le lecteur tongue)
Et donc si on ajoute les 7 carrés de la dernière bande de 4 on pourra toujours mettre 49 carrés 2*2 dans une grille de 20*20.

gnahaha ! smile


Il y a sûrement plus simple.

 #13 - 16-04-2014 01:02:32

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

gâteai 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 : 374

Gâteaau 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.

http://www.prise2tete.fr/upload/dylasse-plaquechoco.jpg

 #15 - 16-04-2014 15:54:47

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2830
Lieu: Luxembourg

âGteau 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 : 4934

Gâteau 7

Je vois qu'on a bien travaillé en mon absence smile

@Cogito : tu devrais pouvoir faire plus simple smile
@Titoufred : oui .
@Dylasse : parfait , très visuel et expéditif .
@Franky : à suivre ... smile

Bon courage à ceux qui cherchent encore .

Vasimolo

 #17 - 17-04-2014 13:45:47

nobodydy
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1354

gâreau 75

arghhh je déteste ce genre de problème lollol
J'ai l'impression que ce n'est pas possible, mais je ne peux pas le démontrer.

et si c'est possible de bloquer le gâteau jaune, ça m’énerve encore plus car je n'y arrive pas.

http://www.prise2tete.fr/upload/nobodydy-gateau75.jpg

je pense que ce n'est pas possible, si je déplace un seul de mes gâteaux, il y aura toujours un espace pour le tien.

Est ce possible ? smile

 #18 - 17-04-2014 18:00:11

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4934

Gâteau 7

@Nobodydy : ton intuition est bonne . Il y a des solutions très courtes , ce qui ne veut pas dire qu'elles sont faciles à trouver smile

Vasimolo

 #19 - 18-04-2014 07:19:24

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3168

gâteay 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 : 4934

Gâteau 57

Je ne crois pas Nogim smile

Vasimolo

 #21 - 19-04-2014 12:46:47

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4934

gâteay 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 smile

Merci à tous pour la participation .

Vasimolo

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Sujet Date Forum
19-09-2010 Enigmes Mathématiques
P2T
Gâteau 44 par Vasimolo
12-11-2011 Enigmes Mathématiques
P2T
Gâteau 90 par Vasimolo
20-01-2015 Enigmes Mathématiques
P2T
Gâteau 28 par Vasimolo
23-08-2010 Enigmes Mathématiques
P2T
Gâteau 74 par Vasimolo
03-04-2014 Enigmes Mathématiques
P2T
Gâteau 93 par Vasimolo
14-02-2015 Enigmes Mathématiques
P2T
Gâteau 60 par Vasimolo
08-06-2013 Enigmes Mathématiques
P2T
Gâteau 56 par Vasimolo
16-11-2012 Enigmes Mathématiques
P2T
Gâteau 55 par Vasimolo
20-08-2012 Enigmes Mathématiques
P2T
Gâteau 68 par Vasimolo
24-01-2014 Enigmes Mathématiques

Mots clés des moteurs de recherche

Mot clé (occurences)

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete