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 - 08-09-2016 15:13:41

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 66

L'ar de couper le papier

Bonjour à tous,

On dispose d'une paire de ciseaux, et d'une feuille de papier rectangulaire.
Cette feuille de papier est constituée de [latex]n\times m[/latex] carreaux, délimités par un quadrillage orthogonal sur toute la feuille. Le but est de découper tout les carreaux de la feuille sans en oublier un seul, de manière à ce qu'il soient tous détachés.
Pour cela, on va utiliser nos ciseaux, qui sont d'un type très particulier:
il ne peuvent que réaliser des coupes franches, c'est à dire qu'il ne peuvent couper qu'en ligne droite (pas de courbe ou de de virage à 90...) et qu'une fois le découpage commencé, il va jusqu'au bout de la feuille, jusqu'à la séparer en deux morceaux.
Ces ciseaux ne sont pas non plus très solides, il ne pourront donc pas découper plus d'une épaisseur de feuille. Pas question donc de superposer les différents morceaux découpés pour aller plus vite. On ne peut pas non plus aligner deux morceaux pour que la coupe franche coupe les deux en même temps, ça compte comme deux coupes franches.

1)Trouver quel est le nombre minimal de coupes franches à réaliser pour découper tout les carreaux.

Je pense que vos aurez tous remarqué qu'à chaque découpe de feuille, certaines coupes franches n'ont une longueur que de 1 (longueur du côté d'un
carreau). On peut toutefois chercher à minimiser ce nombre.

2)Quel plan de découpe permet de minimiser le nombre de coupes franches de longueur 1?

Bon courage smile

si vous avez des questions, n'hésitez pas...



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 08-09-2016 17:57:59

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

L'art de coupe rle papier

nm-1 et le plus économique est de passer par des bandes puis des carrés de 2 de large.

 #3 - 08-09-2016 18:09:16

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 66

L'art de couper le papir

gwen27 très bien!

 #4 - 08-09-2016 19:52:50

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

L'art de coouper le papier

Merci. Ceci dit, avec les règles imposées, la première question n'en est pas une : toute stratégie de découpage prendra nm-1 coups de ciseaux vu que chaque coup de ciseaux ne fait que rajouter une pièce, quelle que soit sa taille ou son format.

Pour la seconde, passer par des morceaux de 2x1 est assez logique même si on peut changer de stratégie suivant la parité des dimensions de la grille. Pour la moitié des morceaux (au moins) il faudra bien découper LE morceau par une coupe de 1

EDIT : (pour chiffrer)
nm/2 coupes de 1  et (nm+1)/2 si m et n sont impairs

 #5 - 09-09-2016 02:59:23

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

L'art de couper le paiper

1) Je trouve que quelque soit la methode que j'utilise, je trouve toujours un nombre de coupes de n*m-1.

2) pour minimiser les coupes de 1, je cherche a couper d'abord des rectangles de 2x1 si possible.
Si par exemple une des dimensions est multiple de 2, je coupe des bandes de 2xn (en faisant des coupes de 'n'), puis des rectangles de 2x1 (en faisant des coupes de 2), puis je termine par (n*m)/2 coupes de 1.
Si les dimensions du  rectangle de depart sont impaires, c'est un peu plus compliqué. je cherche a réduire le rectangle a un carré de 3x3 en enlevant des bandes de 2 par la plus petite longeur.
Finalement , je trouve un nombre de coupes de 1 de (n*m+1)/2


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #6 - 09-09-2016 08:22:48

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

l'ary de couper le papier

Nb de lignes + nb de colonnes, mais chaque fois qu'on coupe une ligne ou une colonne, on ajoute + 1 au nb de découpes, et ceci est à appliquer à chaque noeud puisque le ciseau passe par tous les noeuds.
Nb total de découpes: n-1 + m-1 + (n-1) (m-1) = nm-1

Pour minimiser le nb de découpes L1, on découpe en bandes de largeur 2, elles mêmes découpées en morceaux (1,2). On laisse une dernière bande largeur 3 si les 2 cotés sont impairs, cette bande L3 est découpée en morceaux (2,3) eux mêmes découpés en 3 morceaux (1,2). Restera 1 morceau (1,3). Donc sans avoir fait aucune découpe L1, on a à disposition des morceaux (1,2) et éventuellement un morceau (1,3).
On peut dénombrer maintenant le nb de découpes L1:
Si nm pair, et ni n ni m = 1 alors nm / 2 découpes L1
Si nm impair, et ni n ni m = 1 alors (nm+1)/2 découpes L1
Si n =1 ou m =1 alors nm -1 découpes L1

 #7 - 10-09-2016 10:06:29

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

l'art de coiper le papier

Bonjour,

Question 1
On a [latex]1[/latex] morceau au départ, et on en aura [latex]n\times{m}[/latex] à l'arrivée. À chaque coupe, on ajoute [latex]1[/latex] morceau.
Il faut donc [latex]n\times{m}-1[/latex] coupes.

Le résultat est valable quelle que soit la façon de s'y prendre, même en acceptant de tourner à angle droit au cours d'une coupe.

 #8 - 10-09-2016 11:03:52

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 66

L'rat de couper le papier

nodgim C'est tout bon!
enigmatus Allez, la question 2 maintenant, c'est pas bien plus compliqué... wink

 #9 - 10-09-2016 13:14:55

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

l'zrt de couper le papier

Question 2
Voici ce que je trouve pour le nombre de coupes de longueur 1, en essayant de faire d'abord un maximum de carrés [latex]2×2[/latex]

Code:

m pair,   n pair :   (m×n)/2
m impair, n pair :   ((m+1)n-2)/2
m pair,   n impair : (m(n+1)-2)/2
m impair, n impair : ((m+1)(n+1)-6)/2

 #10 - 10-09-2016 14:28:49

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 66

L'art de copuer le papier

enigmatus On peut faire un peux mieux pour les 3 derniers cas...

 #11 - 10-09-2016 18:15:11

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

l'art de couper le papiet

Effectivement, si l'un des côtés est pair et l'autre impair, je découpe en bandes de 2, et j'obtiens [latex](m×n)/2[/latex].
Je réfléchis au cas (impair,impair).

Édité :
Pour ce dernier cas, je découpe d'abord une bande de largeur 1 sur le plus petit côté.
J'obtiens alors [latex](m×n+min(m,n)-2)/2[/latex]

 #12 - 10-09-2016 18:32:58

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 66

L'art de couper le apier

enigmatus
Pour ton dernier cas, on peut encore améliorer un petit chouias... big_smile

 #13 - 11-09-2016 00:03:44

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

L'art de couper le papir

caduk #12 a écrit:

enigmatus
Pour ton dernier cas, on peut encore améliorer un petit chouias... big_smile

En découpant le cas (impair,impair) en un cas (pair,impair) et un cas (impair,impair), de différentes façons, il semblerait (au moins jusqu'à (9,9), que la réponse cherchée soit [latex](m×n+1)/2[/latex]. Je ne vois pas comment le démontrer.

 #14 - 11-09-2016 00:23:11

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 66

L'art de coupr le papier

enigmatus C'est effectivement la bonne réponse. Pour trouver un exemple de découpage, tu étais bien parti avec ta méthode, il faut juste la creuser un peu plus. Pour démontrer que l'on ne peut pas faire plus bas (que ce soit dans ce cas ou l'autre) un simple argument suffit, et je crois que personne ne l'a vraiment dit, du moins exposé clairement...

 #15 - 11-09-2016 08:36:24

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

L'art de couper le papeir

Je pense que la nuit m'a porté conseil.
Une coupe de longueur 1 est optimisée quand elle partage un domino de 2 cases.
Si [latex]m×n[/latex] est pair, on a [latex](m×n)/2[/latex] dominos.
Si [latex]m×n[/latex] est impair, on a [latex](m×n-1)/2[/latex] dominos, et il faut au moins une coupe de plus pour séparer la case qui reste.

 #16 - 11-09-2016 08:48:52

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

L'art de coupr le papier

Tu parles du passage par des pièces de dimension 2x1 ?

Chaque morceau final a demandé une coupe de largeur 1.
Donc, le plus économique est de faire 2 morceaux avec cette coupe (difficile de faire plus)

Si une dimension de la grille est paire, il suffit donc de couper selon l'autre pour avoir des bandes de longueur paire et de largeur 2, que l'on coupe en morceaux de 2x2. (Si on ne fait pas des bandes de largeur 2, on multiplie les coupe de longueur 1)

On recoupe ces morceaux en 2, et on obtient mn/2 morceaux de 2x1.

Si les deux dimensions de la grille sont impaires, on procède de la même façon en prenant bien soin de laisser une bande de largeur 3.
Les bandes de largeur 2 ne posent pas de problème.

Celle de largeur 3 peut être découpée en bandelettes de largeur 2 qui ne poseront pas de souci non plus. Il restera juste un morceau de 3x1 qui nous coutera une coupe unitaire. ==> (mn+1)/2

Le seul cas ou ça ne marche pas, c'est si m ou n=1

 #17 - 11-09-2016 10:41:34

caduk
Passionné de Prise2Tete
Enigmes résolues : 37
Messages : 66

'art de couper le papier

Très bien enigmatus et gwen

 

Réponse rapide

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

Répondez (numériquement) à la petite énigme suivante : 

Dans une course, vous doublez le 42ème, en quelle position êtes-vous ?

Sujets similaires

Sujet Date Forum
06-10-2015 Enigmes Logiques
P2T
Sudoku 2 par SaintPierre
11-04-2011 Enigmes Logiques
P2T
Maux croisés par SaintPierre
31-03-2011 Enigmes Logiques
P2T
04-04-2011 Enigmes Logiques
P2T
04-07-2014 Enigmes Logiques
P2T
V3ck par darkeye
10-06-2015 Enigmes Logiques
16-06-2008 Enigmes Logiques
11-07-2009 Enigmes Logiques
P2T
31-08-2010 Enigmes Logiques

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