Enigme L'art de couper le papier @ Prise2Tete

caduk · #1

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

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

gwen27 · #2

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

caduk · #3

gwen27 très bien!

gwen27 · #4

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

dhrm77 · #5

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

nodgim · #6

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

enigmatus · #7

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.

caduk · #8

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

enigmatus · #9

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

caduk · #10

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

enigmatus · #11

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]

caduk · #12

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

enigmatus · #13

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.

caduk · #14

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

enigmatus · #15

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.

gwen27 · #16

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

caduk · #17

Très bien enigmatus et gwen

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 08-09-2016 15:13:41

l'aet de couper le papier

#0 Pub

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

L'art de couper le apier

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

l'art de couper le pzpier

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

L'ar tde couper le papier

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

L'art de coouper le papier

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

L'art ed couper le papier

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

l'att de couper le papier

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

l'art de couprr le papier

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

L'art de couper le paper

Code:

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

m'art de couper le papier

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

l'art dz couper le papier

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

L'art de coper le papier

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

l'art de xouper le papier

caduk #12 a écrit:

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

L'art de couper lle papier

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

L'art de couer le papier

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

L'art de couper le ppaier

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

'art de couper le papier

Réponse rapide

Sujets similaires

Pied de page des forums