Paquet cadeau

Placer le ruban d'un paquet cadeau sans changement de direction, mais passant par toutes les faces du paquet, et sans qu'il ne se détende en glissant.

Le ruban étant tendu, entre deux points du ruban il y a alors la plus courte distance possible : géodésique.
Le ruban trace ainsi une ligne droite sur un patron déplié du paquet.

Parmi les divers agencements de faces pour former un patron, il faut en choisir un qui permette une droite entière "périodique", sans déborder du patron.
La solution la plus simple est celle ou la période est le parcours une seule fois de chaque face :

Les points AB étant les mêmes points (sur la face verte) le ruban rouge BB ne peut varier que parallèlement à lui même dans les limites imposées par les coins critiques, soit entre les deux droites limites vertes.
La longueur de cette droite étant constante, le ruban peut glisser jusqu'au coin critique et là, se défaire. Mais il y avait déjà le même inconvénient pour le trajet orthogonal classique.

L'angle du ruban est tan(α) = (a + c)/(a + 2b + c)
Les trajets critiques donnent alors : tan(α) < min (a/c, c/a).

Posons x = b/a et y = c/a, il vient :

1 - 2xy < y² < 1 + 2x

le tracé est possible seulement si x,y est dans les régions :
y² - 2x -1 < 0 délimitée par une parabole d'axe Ox
et y² + 2xy - 1 > 0 délimitée par une hyperbole d'asymptotes y = 0 et y = -2x
soit la région entre ces deux courbes. Sinon permuter a,b,c, ce qui n'est pas toujours possible :
avec les dimensions 1×4×5, aucune permutation de ces valeurs ne satisfait au critère ci-dessus.
Notons que a et c sont interchangeables (cela revient à échanger les faces vertes et grises sur le trajet).
Il n'y a donc que trois permutations à essayer, et on peut ainsi imposer a ≤ c.

La longueur du ruban est d² = (a + c)² + (a + 2b + c)²

Selon le choix (permutations de a,b,c) effectué, cette longueur peut être différente.
Par exemple avec 2×3×4, les trois permutations donnent :
a = 2, b = 3, c = 4, d = 13.4164
a = 3, b = 2, c = 4, d = 13.0384 ← la plus petite
a = 2, b = 4, c = 3, d = 13.9283

Un script pour calculer les longueurs :

Version animée du patron (avec applets JavaSketchpad)

Ce n'est pas le seul trajet passant une fois par face. Le trajet précédent traverse des faces (vertes et grises) "de part en part", c'est à dire entre et sort d'une face par deux arêtes opposées.
Mais on peut aussi traverser chaque face par deux arêtes partageant un sommet :

α = 45°
d =(a+b+c)√2
b - a ≤ c ≤ b + a

Avec les valeurs précédentes, a = 2, b = 3, c = 4 (3-2 < 4 < 3+2) donne d = 12.7279, plus court que le trajet précédent.

Autres trajets

Ce trajet "à l'économie" avec le plus court ruban possible faisant un peu pingre sur un paquet cadeau, on peut chercher à "entourer" d'avantage le paquet cadeau avec le ruban.
Le trajet diagonal classique fait passer le ruban deux fois sur chacune des "grandes" faces du paquet :

Sur le patron, ceci se matérialise par une duplication des faces rouges et magenta, et des trajets "fantômes" en dehors du tracé principal.
Le trajet est symétrique par rapport au centre de la face grise, et de plus la période est d'un demi tour seulement (face grise ≡ face verte), les limites sont ainsi obtenues avec juste tan(α) ≤ c/a.

tan(α) = (a + c)/(a + b)
d² = 4(a + c)² + 4(a + b)²
a² < bc

Cette condition est a fortiori satisfaite si a est le plus petit côté (il y a donc toujours une solution au moins). Mais dans certains cas a peut être > b ou c. Si a est le plus grand côté c'est par contre clairement impossible.
Avec les notations ci-dessus (x = b/a, y = c/a) la zone possible est au delà de l'hyperbole équilatère xy = 1.
L'échange de b et c donne le même trajet, tourné de 90°.
Il suffit de tester le seul cas b≤a≤c (a≤b≤c étant toujours possible)

Un script pour calculer les longueurs :

Passages multiples

Trouver un trajet du ruban qui passe au moins deux fois par chaque face.

Dans ce cas, le plus court trajet se recoupe et par exemple :

Pour réaliser une maquette, les 6 "premières" faces suffisent pour construire le paquet : les autres sont des images répétées de ces faces.
Le trajet est symétrique par rapport au centre de la face rouge. On a ainsi les conditions limites (trajets en vert).

tan(α) = (a + b + 2c)/(5a + 3b + 2c)
d² = (a + b + 2c)² + (5a + 3b + 2c)²
b/(3a + 2c) < tan(α) < b/(a + 2c)
et tan(α) > a/b

Avec les mêmes conventions que ci-dessus pour x et y, les limites sont les hyperboles
4y² - 3x² + 8y - 2x + 3 > 0 (en bleu)
4y² - 3x² + 4y - 4x + 1 < 0 (en rouge)
et x² + 2xy - 2x - 2y - 5 > 0 (magenta)

Ces hyperboles se coupent en P₁ (1+√2, √2) et P₂ (2.1958, 1.9108) (x, y>0)

Il est donc nécessaire que c/a>√2 et b/a > 2.1958 (sinon aucun espoir d'être dans la zone bleue).
a est donc forcément la plus petite des trois dimensions.
On a aussi c/b < y₂/x₂ = 0.87 et donc a < c < b et par conséquent c'est impossible avec un cube.

Un script pour calculer les longueurs :

Là aussi il y a d'autres trajets possibles. Celui-ci passe par 14 faces, soit deux des faces trois fois, et les autres deux fois.

Généralisation

On peut finalement s'intéresser à tous les trajets possibles.
Une première approche est topologique : recenser tous les trajets cycliques, indépendamment de l'alignement des segments.
Considérons le graphe qui a pour sommets les faces du parallèlépipède, deux sommets étant reliés si les faces partagent une même arète. Dans l'espace on obtient le solide dual du parallèlépipède : l'octaèdre.
Le graphe peut "s'aplanir" en la représentation ci contre. Un trajet est alors un cycle sur ce graphe.
Mais tous les cycles ne conduisent pas à un trajet rectiligne !

Un trajet qui passe par toutes les faces (tous les sommets du graphe dual) une fois et une seule est donc un cycle hamiltonien sur l'octaèdre dual.
Aux symétries de l'octaèdre près, il n'existe que deux circuits hamiltoniens sur l'octaèdre : ABCDEFA et ABDCEFA. Ils sont réellement différents et correspondent aux deux trajets vus au début : celui qui ne passe que par des arètes adjacentes, et celui où deux faces sont traversées de part en part.
Le trajet hamiltonien sépare l'octaèdre obligatoirement en deux ensembles de 4 faces (formule de Grinberg, F₃-G₃ = 0).

Il n'existe que 3 façons d'agencer 4 faces triangulaires connexes : les 3 "tétramants".
Mais le tétramant concave, plaqué sur l'octaèdre donne ABDEA, qui ne passe pas par C et F.
Il n'y a donc bien que ces deux circuits possibles.

Pour des passages multiples par les différentes faces, les cycles ne sont plus hamiltoniens, et il existe de nombreuses solutions, sous l'angle topologique.
Une fois choisi un parcours "topologique" (ordre de succession des faces), il reste à placer ces faces sur un patron correspondant à cet ordre de succession. Puis à étudier les conditions d'alignement pour que le trajet ne sorte pas du patron.

Une autre façon de voir les choses est de considérer la face de départ et la face d'arrivée finale (identiques donc) sur Z²[a,b,c].
Simplifions le problème en prenant un cube. La superposition de tous les patrons possibles donne alors un quadrillage du plan Z².
Considérons un cube sur le carré (0,0) et faisons le rouler sur le plan, toujours en avant ou vers la droite. On obtient ainsi un patron (généralisé) du cube.
Pour que ce patron convienne il est nécessaire que sur la case d'arrivée, le cube ait exactement la même orientation qu'au départ. Notons l'orientation du cube en orientant trois arêtes d'un trièdre.
Disons a,b,c (pour étendre au parallèlépipède...)
En faisant rouler vers la droite (sens X) son orientation devient (-b,a,c)
En faisant rouler vers l'avant (sens Y), elle devient (-c,b,a)
Il n'y a bien sûr que 24 orientations possibles, et non 3!*2³ = 48. Les 24 autres correspondant à l'image de notre cube dans un miroir.

En décalant l'origine sur une nouvelle position de même orientation, on peut copier la liste des positions déja obtenues, de proche en proche.
A partir d'un certain nombre de déplacements X et Y, les cases ayant une orientation identiques forment ainsi un damier (x+y=0 mod 2).

Le nombre de faces traversées par le ruban est le nombre de déplacements X+Y.
Un même nombre de faces traversées correspond ainsi à des cases alignées sur une diagonale x+y = n.
Traverser 4 faces ne donne que les deux solutions triviales XXXX et YYYY, cases (4,0) et (0,4) (un tour de ruban à 90°).
Traverser 6 faces donne les cases (4,2) et (3,3) - et la symétrique (2,4).
On notera qu'il y a à priori (x+y)!/(x! y!) chemins pour atteindre la case (x,y) soit pour atteindre la case (4,2) : 6!/(2!*4!) = 15.
En fait 3 seulement conduisent à un cube correctement orienté : XXYXXY, XYXXYX, YXXYXX
Mais si on fait plusieurs tours superposés de ruban, on obtient :
XXYXXYXXYXXYXXYXXY...
XYXXYXXYXXYXXYXXYX...
YXXYXXYXXYXXYXXYXX...
Qui représentent en fait le même trajet cyclique.

De même pour atteindre la case (3,3) seuls 2 chemins sur 20 conviennent : YXYXYX, XYXYXY, symétriques l'un de l'autre.

On retouve ainsi les deux seules solutions, aux symétries près, traversant exactement 6 faces (donc une fois chaque face).
- case (4,2) XYXXYX correspondant au premier patron indiqué : traversée de deux faces de part en part.
- et case (3,3) XYXYXY correspondant à la traversée d'arêtes consécutives.

On peut s'intéresser maintenant au cas de 8 faces traversées :
il n'y a que la seule case (4,4), en dehors des rubans bêtement superposés de (8,0) et (0,8).
Les seuls trajets convenables pour atteindre (4,4) sont :
XYYXXYYX et ses dérivés (permutation circulaire, échange de X et Y)
et le sans intérêt XXXXYYYY et ses dérivés, celui-ci ne pouvant conduire à un ruban rectiligne.
La solution avec 8 faces traversées proposée précédement (diagonal classique) est donc unique.

A partir de 10 faces traversées, on atteint la zone où une case sur deux est accessible, tout au moins avec 4 X et plus, et 4 Y et plus.
Intéressant et non encore étudié ci-dessus, le cas de 12 faces traversées, pour obtenir des trajets où chaque face est traversée exactement deux fois.

Les cases concernées sont :
- (12,0) bof ! seules 4 faces sont traversées par 3 tours de ruban superposés !
- (9,3) XXXYXXXYXXXY, donnant bien entendu une première solution 'triviale' et symétrique.

- (8,4) XXXXXXXXYYYY, XXXXYXXXXYYY, XXXXXXYYXXYY, XXXXYYXXXXYY, XXXXYXXYYXXY et XXXYXXYXYXXY impossibles si a=b=c,
XXYXXYXXYXXY = (XXYXXY)² double de la case (4,2), c'est à dire le ruban passe deux fois sur le trajet à 6 faces.

- (7,5) XXXYXYXXXYYY, XXXYXXYYXYXY, XXXYXYXYYXXY et XXYXXYXYXYXY impossibles avec a=b=c.

- et (6,6) XXXYXXYYYXYY, XXXYYXYYYXXY, XXXYYYXXYXYY, XXXYYXYXXYYY, XXYXXYXYYXYY, XXYXXYYXYYXY et XXYXYXYYXYXY impossibles avec a=b=c,
XYXYXYXYXYXY = (XYXYXY)² double de la case (3,3).

Avec un cube (a=b=c) il n'y a donc pas d'autre solution.
C'est un peu plus compliqué si a,b,c différents car certains trajet rejetés deviennent peut-être possibles.
Il faut les essayer et calculer le domaine de validité {c/a, b/a} comme au début, et ne rejeter le trajet que si ce domaine est vide (aucune valeur des dimensions ne convient).
Voir comme exemple le passage par 14 faces étudié précédemment, le cube est impossible, mais c'est possible avec certaines dimensions !
Le patron XXXXYYXXXXYY (8,4) est le seul autre possible pour 12 faces. Mais s'il passe bien par 12 faces au total, ce n'est pas 2 fois sur chaque ! Il y a deux faces où il ne passe qu'une fois, et deux où il passe trois fois.

Annexe - liste des patrons possibles

Liste des rotations et liste des faces, ainsi que la valeur de tan(α) pour un parallèlépipède a×b×c, non simplifiée de sorte que la distance est d² = num² + den².

La face 1 posée sur la case de départ est de dimensions b×c, la face 2, devant, de dimension a×b, et la face 3, à gauche, de dimension a×c. Le numérotage des faces correspond à celui d'un dé ordinaire (somme des faces opposées = 7).

La liste des rotations indiquée est la première d'une famille de rotations équivalentes.

Seules sont listés ici les patrons où un trajet rectiligne est possible, pour certaines dimensions.
Les trajets où le ruban fait plusieurs tours sur lui même sont omis, ainsi que les trajets "triviaux" à 90°.


===============
Longueur = 6
===============
[4, 2]  XXYXXY, 1465321, tan(α) = (a+c)/(a+2b+c)
[3, 3]  XYXYXY, 1456321, tan(α) = (a+b+c)/(a+b+c) = 1

===============
Longueur = 8
===============
[4, 4]  XXYYXXYY, 146513621, tan(α) = (2a+2c)/(2a+2b) = 1

===============
Longueur = 10
===============
[8, 2]  XXXXXXYXXY, 14631465321, tan(α) = (a+c)/(3a+4b+c)
[7, 3]  XXXXXYXYXY, 14631456321, tan(α) = (a+b+c)/(3a+3b+c)
[6, 4]  XYXXXXYXYY, 14562153621, tan(α) = (a+b+2c)/(3a+b+2c)
[6, 4]  XXXYYXXXYY, 14635413621, tan(α) = (a+b+2c)/(3a+3b)
[5, 5]  XYXXXYXYYY, 14562135621, tan(α) = (2a+b+2c)/(2a+b+2c) = 1

===============
Longueur = 12
===============
[9, 3]  XXXYXXXYXXXY, 1463512645321, tan(α) = (a+b+c)/(3a+3b+3c) = 1/3
[8, 4]  XXXXYYXXXXYY, 1463156413621, tan(α) = (2a+2c)/(4a+4b) = 1/2

===============
Longueur = 14
===============
[12, 2] XXXXXXXXXXYXXY, 146314631465321, tan(a) = (a+c)/(5a+6b+c)
[12, 2] XXXXXXYXXXXXXY, 146314653245321, tan(a) = (a+c)/(3a+6b+3c)
[11, 3] XXXXXXXXXYXYXY, 146314631456321, tan(a) = (a+b+c)/(5a+5b+c)
[11, 3] XXXXXYXXXXXYXY, 146314562156321, tan(a) = (a+b+c)/(5a+3b+3c)
[10, 4] XYXXXXXXXXYXYY, 145621562153621, tan(a) = (a+b+2c)/(5a+b+4c)
[10, 4] XXXYXXXXYXXXYY, 146351265413621, tan(a) = (a+b+2c)/(5a+3b+2c)
[10, 4] XXXXXYYXXXXXYY, 146314536413621, tan(a) = (a+b+2c)/(5a+5b)
[10, 4] XXXXYXYXXXXYXY, 146315462156321, tan(a) = (2a+b+c)/(4a+3b+3c)
[9, 5]  XYXXXXXXXYXYYY, 145621562135621, tan(a) = (2a+b+2c)/(4a+b+4c)
[9, 5]  XXXYXXXYXYXXYY, 146351264513621, tan(a) = (2a+b+2c)/(4a+3b+2c)
[9, 5]  XXYXYXXXYXXXYY, 146531265413621, tan(a) = (2a+b+2c)/(4a+3b+2c)
[8, 6]  XYXXXXXXYXYYYY, 145621562315621, tan(a) = (2a+b+3c)/(4a+b+3c)
[8, 6]  XXYXXYXXYYXXYY, 146532146513621, tan(a) = (3a+3c)/(3a+4b+c)
[8, 6]  XXYXYXXYXYXXYY, 146531264513621, tan(a) = (3a+b+2c)/(3a+3b+2c)