!! Be careful, hachure is a concept which is rather aimed at the fans of complexity and technical reflection !!
Before we leaf our old bud-dy, I want to thank Kcenia for having motivated and inspired me this season.
May contain traces of trees.
Difficulty : ***
Tested, logical.
Don't require any specific method.
Good blackenage.
Allez, je reprends tous ceux que je n'ai pas encore réussi à résoudre!!
Thank you :)
@Kcenia : Généralement, je commence par l'image puis j'ajuste. Si je veux utiliser le principe de la borne, je m'arrange pour qu'aucun trait ne s'arrête sur une interligne d'où part un autre trait. Sinon, la condition n'est pas respectée et le principe ne peut pas être utilisé.
Ensuite, je regarde les nombres en en-tête. Si je vois deux nombres égaux, je vérifie que les traits correspondants ne puissent pas permuter de manière triviale. J'essaie aussi d'aligner un maximum de traits de même longueur si l'image s'y prête, histoire de simplifier les choses. Enfin, je me lance dans une session plus ou moins longue de tests/ajustements.
@Tipilu : Je ne sais plus comment je suis arrivé dessus. Je crois que c'est à force d'appliquer les principes de la vague, parfois simultanément sur plusieurs lignes (comme dans le 48). Je fonctionne beaucoup par intuition-démonstration.
Et effectivement, il se démontre. Je ne me serais pas permis de l'utiliser sinon.
Attention : démonstration brouillon et imbuvable dans un espace inadapté à son écriture dans 3, 2, 1...
(J'ai fait ce que j'ai pu ; j'espère ne pas m'être emmêlé dans les nombres.)
Pour chaque i de 0 à n, notons :
* a_i le nombre de lignes dont la i-ème interligne est remplie ainsi o|x (Arrêt)
* b_i le nombre de lignes dont la i-ème interligne est remplie ainsi x|x (Blanc)
* c_i le nombre de lignes dont la i-ème interligne est remplie ainsi o|o (Continu)
* d_i le nombre de lignes dont la i-ème interligne est remplie ainsi x|o (Départ)
* N_i le nombre total de cases noires dans la i-ème ligne
avec o pour une case noire et x pour une croix.
Notes :
* Tous ces nombres sont positifs.
* a_0=0, c_0=0, b_n=0, d_n=0, N_0=0 et N_(n+1)=0
* Pour tout i, a_i+b_i+c_i+d_i=m, où m est le nombre de colonnes.
* c_(i-1)+d_(i-1)=N_i=a_i+c_i
* En réécrivant la note précédente, N_(i+1)=c_i+d_i, d'où N_(i+1)-N_i=d_i-a_i
* Par définition des traits, T=somme(a_i), et T=somme(d_i)
Premier principe de la vague :
* Si N_(i+1)-N_i=k>0, alors il y a au moins k traits qui démarrent sur la i-ème interligne.
* Si N_(i+1)-N_i=-k<0, alors il y a au moins k traits qui s'arrêtent sur la i-ème interligne.
Preuve :
* Si N_(i+1)-N_i=k>0, alors d_i>=k+a_i>=k
* Si N_(i+1)-N_i=-k<0, alors a_i>=k+d_i>=k
Deuxième principe de la vague :
Si N_(i+1)=N_i et a_i=0, alors chaque croix placée dans la i-ème ligne implique une croix dans la case située juste en dessous et vice-versa.
Preuve :
Comme N_(i+1)=N_i, alors d_i-a_i=0. D'où, d_i=a_i=0.
Lemme :
Notons A l'ensemble des i tels que N_(i+1)-N_i<0.
Notons D l'ensemble des i tels que N_(i+1)-N_i>0.
somme{N_i-N_(i+1)}{i dans A}=somme{N_(i+1)-N_i}{i dans D}
Preuve :
somme{N_(i+1)-N_i}{i de 0 à n}=N_n-N_0=0-0=0 (somme télescopique)
or somme{N_(i+1)-N_i}{i de 0 à n}=somme{N_(i+1)-N_i}{i dans A}+somme{N_(i+1)-N_i}{i dans D}+somme{0}
D'où, somme{N_(i+1)-N_i}{i dans D}=-somme{N_(i+1)-N_i}{i dans A}=somme{N_i-N_(i+1)}{i dans A}
Principe de la borne :
Si somme{N_(i+1)-N_i}{i dans D}=T (condition de la borne), alors aucun trait ne peut s'arrêter sur la i-ème interligne si i n'est pas dans A, et aucun trait ne peut démarrer sur la i-ème interligne si i n'est pas dans D.
De plus, pour tout i dans A, N_i-N_(i+1)=a_i et pour tout i dans D, N_(i+1)-N_i=d_i
Preuve :
* D'après le premier principe de la vague, pour tout i dans D, N_(i+1)-N_i<=d_i (E1)
D'où, T=somme{N_(i+1)-N_i}{i dans D}=<somme{d_i}{i dans D}
De plus, somme{d_i}{i dans D}=<somme{d_i}=T car tous les d_i sont positifs.
Ainsi, somme{d_i}{i dans D}=T=somme{d_i} (E2)
Comme les d_i sont positifs, alors pour tout i qui n'est pas dans D, d_i=0
* Par ailleurs, on vient de voir que :
pour tout i dans D, d_i-[N_(i+1)-N_i]>=0 (car E1)
et somme{d_i-[N_(i+1)-N_i]}{i dans D}=0 (car E2 et hypothèse de départ)
Comme on a une somme nulle de termes positifs,
alors pour tout i dans D, d_i-[N_(i+1)-N_i]=0
* La condition de la borne est équivalente à somme{N_i-N_(i+1)}{i dans A}=T (d'après le lemme)
On peut donc démontrer de même que :
pour tout i qui n'est pas dans A, a_i=0
et pour tout i dans A, a_i-[N_i-N_(i+1)]=0
CQFD
La i_ème interligne est la frontière entre les (i-1)-ème et i-ème lignes.
Je te remets l'image que j'ai utilisée dans la description du 156 : https://lutim.stolon.fr/ODsGfygfRdzD2MAO.png
Elle devrait aider à y voir plus clair. Les interlignes y apparaissent en pointillés. La légende est donnée dans le 156.
Bonne lecture ;)