Problème du bûcheron

Il y a quelques jours, je taille mes arbres (noisetier, pommier, ...) dont les jeunes pousses commencent à devenir bien hautes. Je me retrouve avec une cinquantaine de tiges de plusieurs mètres de long à débiter en bûchettes. Je souhaite que toutes les bûchettes aient à peu près la même taille (50 cm), mais hors de question de tout mesurer : je fais cela au jugé. Quand la tige est longue, me dis-je, difficile de savoir si sa longueur est un multiple de 50 cm ; il semble raisonnable de juste couper une bûchette de 50 cm et de recommencer, ce, tant que la tige est "longue". A force de couper, elle devient suffisamment courte pour que je puisse estimer si sa longueur est un multiple de 50 cm, et comme généralement ce n'est pas le cas, je dois changer de méthode pour éviter qu'il me reste un morceau de taille incorrecte sur les bras à la fin. Ma méthode pour poursuivre consiste alors à diluer l'excès ou le défaut de longueur parmi les morceaux restant à couper pour qu'ils soient tous de la même taille, la plus proche possible de 50 cm. Enfin, quand la tige finit par avoir une taille égale ou inférieur à 50 cm, inutile de tourner autour du pot, ce qui reste est la dernier bûchette :)

<<<<<<<<<<< AVANT ; ... ; APRES >>>>>>>>>>>

Mon penchant pour les maths prend alors le dessus. Sécateur à la main : soit \( x \) la taille de la tige. Clac clac, coupé. Soit \( u \) l'unité de longueur souhaitée d'une bûchette (\( u = 50 \mbox{cm} \)), ce qui s'appelle aussi l'aune (n'est-ce pas, papa ?). Tant que \( x \) est grand, j'applique la méthode n°1 "\( x \) devient \( x - u \)". J'entasse. Dès que \( x \) est suffisamment petit, j'applique la méthode n°2 dans laquelle j'encadre \( x/u \) entre deux entiers successifs :

\[ n_1 = \lfloor x/u \rfloor < x/u < \lceil x/y \rceil = n_2 = n_1 + 1 \]

Si je choisis de couper \( x \) en \( n_1 \) morceaux, les morceaux auront pour taille \( L_1 = x / n_1 \) ; mais si je choisis de couper \( x \) en \( n_2 \) morceaux, les morceaux auront pour taille \( L_2 = x / n_2 \) ; on a donc :

\[ L_1 = \frac{x}{\lfloor x/u \rfloor} \] \[ L_2 = \frac{x}{\lceil x/u \rceil} \] \[ L_1 > L_2 \]

Selon moi, la distance usuelle calculée comme valeur absolue de la différence de taille, \( d(L_i,u) = \left | L_i - u \right | \), est inappropriée pour dire qui de \( L_1 \) ou de \( L_2 \) est le plus proche de \( u \), car on souhaite comparer des ordres de grandeurs et non des écarts. Qui dit ordre de grandeur dit passage au logarithme et je définis ma distance comme suit :

\[ d(L_i, u) = \left| \ln(L_i) - \ln(u) \right | = \left | \ln \left ( \frac{L_i}{u} \right ) \right | \]

La méthode n°2 revient alors à choisir le \( i \) (1 ou 2) qui minimise \( d(L_i, u) \).

Maintenant, ce n'est pas très rigoureux d'utiliser des expressions comme "tant que \( x \) est grand" ou "dès que \( x \) est suffisamment petit". Y aurait-il un seuil \( x_s \), tel que \( x \) est grand quand \( x > x_s \) et \( x \) est petit quand \( x < x_s \) ? Je trouve cela arbitraire et brutal. Je préfère une transition en douceur, c'est pourquoi je vais pondérer ma méthode à l'aide d'une fonction tangente hyperbolique. Cela signifie en quelque sorte, que j'applique un mélange de méthode 1 et de méthode 2, où la proportion de méthode 1 est d'autant plus grande que \( x \) est grand. De toute façon, même en évitant d'introduire des seuils dans mes définitions, des seuils (d'une autre nature) vont surgir d'eux-mêmes, comme nous le verrons plus loin :)

Un dernier raffinement : d'un bûcheron à l'autre, la capacité d'anticipation n'est pas nécessairement la même : la transition vers la méthode 2 s'opère plus tôt (= quand \( x \) est encore grand) pour un bûcheron qui anticipe bien, par rapport à un bûcheron qui anticipe mal. Matérialisons cette capacité d'anticipation par un paramètre \( a \) dans la fonction tangente hyperbolique. Quand je mets toutes ces élucubrations bout à bout dans un langage de programmation (PARI en l'occurrence) et que je simule, cela donne :

Code :


d(x,y)=abs(log(x/y))
decoupage_entier(u,x)=my(n1=floor(x/u),n2=ceil(x/u),L1,L2);if(n1==0,[1,x],L1=x/n1;L2=x/n2;if(d(L1,u)<d(L2,u),[n1,L1],[n2,L2]))
couper_buchette(x,a,u)=my(e,n,L,t);e=decoupage_entier(u,x);n=e[1];L=e[2];if(n==1,x,t=tanh(a*x/u);t*u+(1-t)*L)
tronconner(x,a,u)=my(dx);while(x!=0,dx=couper_buchette(x,a,u);print1(dx,"\n");x-=dx)

Trace d'exécution, pour un bûcheron qui anticipe mal :


tronconner(3.33,1,0.5)
0.49999992027809547921403024300382864124
0.49999931275985261035929300604537977266
0.49999390684630901200635838994027529253
0.49994375726846090899335607024877210486
0.49944853115808296048610178208571349549
0.49410390958462813722161949001370798570
0.33651066210457089171924101866232270755

Trace d'exécution, pour un bûcheron qui anticipe moyennement :


tronconner(3.33,0.33,0.5)
0.49940833849949057495107130841538898775
0.49868510312752340948618515667212601428
0.49704027785374068683660987644663182130
0.49327008767225727555296132102466329132
0.48464226786461835757693491326065170103
0.46510483223349852739661193910756532386
0.39184909274887116819962548507297286049

Trace d'exécution, pour un bûcheron qui anticipe (divinement) bien :


tronconner(3.33,0,0.5)
0.47571428571428571428571428571428571429
0.47571428571428571428571428571428571429
0.47571428571428571428571428571428571429
0.47571428571428571428571428571428571429
0.47571428571428571428571428571428571429
0.47571428571428571428571428571428571429
0.47571428571428571428571428571428571429

Trace d'exécution prouvant que la taille des bûchettes peut aussi partir à la hausse :


tronconner(3.66,0.33,0.5)
0.50036177440615766811997477379214542939
0.50080916884024594300399049888149777732
0.50184488080807120542412137271970637214
0.50430334779510683966978253020393610107
0.51032332221267388367169793867502911226
0.52580207793645632975004753997398899002
0.61655542800128813036038534575369621783

Trace d'exécution prouvant l'émergence de seuils (attention j'ai mis \( u = 1 \) pour changer) :


tronconner(sqrt(2)-0.0001,0.1,1)
1.4141135623730950488016887242096980786
tronconner(sqrt(2)+0.0001,0.1,1)
0.74830003277842022306414343029945279769
0.66601352959467482573754529391024528088

Il suffit d'un petit changement quantitatif sur \( x \) (ici deux dixièmes de millimètre) pour obtenir un changement qualitatif (je coupe ou ne coupe pas).

La méthode n°2 a en effet un dilemme quand \( d(L_1, u) = d(L_2, u) \). Et si \( n_1 = 1 \) cela se traduit par

\[ x = n_1 L_1 = L_1 = n_2 L_2 = 2 L_2 \] \[ L_1 / u = u / L_2 \] \[ x / u = u / (x / 2) \] \[ x = \sqrt{2} u \]

ce qui explique le 1.414

Quels sont les seuils dans le cas général, i.e. les valeurs de \( x \) provoquant une discontinuité dans la méthode n°2 (pour un bûcheron qui anticipe divinement bien) ? Le système d'équations à résoudre est :

\[ x = n_1 L_1 = n_2 L_ 2 \] \[ L_1 / u = u / L_ 2 \]

Sa solution est :

\[ x/u = \sqrt{ n_1 n_2 } = \sqrt{ \lfloor x/u \rfloor \lceil x/u \rceil } \]

Il y a un seuil \( x_n = \sqrt{n(n+1)} u \) pour chaque \( n \in \mathbb{N}^{*} \)

La fonction qui donne la taille des bûchettes du bûcheron divin en fonction de la taille de la tige, toutes dimensions rapportées à \( u \), est illustrée ci-dessous :

Elle peut être définie par morceaux comme ceci :

\[ \bbox[white, border: 1px solid red]{ \forall n \in \mathbb{N}^{*}, \forall x \in \left ] \sqrt{(n-1)n}, \sqrt{n(n+1)} \right [, f(x) = \frac{x}{n} } \]

Et pour finir, connaissez-vous la blague du Juge Sécateur ?

Non ?

COUPABLE !

LR, 22/05/2021.