J'ai une démonstration complète que je dois mettre au propre . En fait c'est celle d'Ocha ( lien fourni ) , j'ai simplement comblé les multiples lacunes

Je rédige ça dans la semaine .

Il est vraiment joli ce problème !!!

Vasimolo

J'ai un peu de mal à comprendre la preuve. Tu vas peut-être pouvoir m'apporter quelques éclaircissements.

Première question : en bas de la 1e page, sur ton dessin, tu ne traces qu'une partie des flèches, concernant seulement une partie des pépites placées dans chaque angle. Peux-tu expliciter la règle qui fait que tu traces ou non telle ou telle flèche ?

Ça ne répond pas à ma question, je vais la reformuler.

Dans ton exemple, de gauche à droite, les colonnes contiennent initialement 2,2,3,1,1,3 pépites, et de haut en bas, les lignes contiennent initialement 3,1,2,2,1,3 pépites. J'en déduis que c'est pour cela que tu ne traces que les flèches qui vont d'une ligne à 3 pépites vers une ligne à 1 pépite, et idem pour les colonnes.

Mais, en général, quelle règle emploies-tu pour savoir quelles flèches tracer ? Ce n'est pas si évident. Par exemple, j'ai sous la main un exemple de gâteau de taille 12x12, où les les trois premières lignes contiennent respectivement 6, 3 et 4 pépites. Chaque ligne devant contenir 4 pépites à la fin, cela implique qu'il faut tracer des flèches allant de la ligne à 3 pépites vers la ligne à 4 pépites...

Donc, si je comprends bien, tu regardes les lignes 1 à k : si elles contiennent plus de 3k pépites, tu traces les flèches [ligne k]--->[ligne k+1], si elles contiennent moins de 3k pépites, tu traces les flèches [ligne k+1]--->[ligne k], et si elles contiennent 3k pépites exactement, tu ne traces pas de flèche entre la ligne k et la ligne k+1. Et idem pour les colonnes.

Si c'est bien cela, c'est OK pour la première page.

Pour la page 2, il faut encore que j'y réfléchisse. Pourrais-tu fournir un exemple avec un gâteau plus grand que 6x6 ? Je pense que ça aiderait vraiment.

@Ebichu : Tu as bien compris et il n'y a rien de difficile dans la deuxième page même si l'idée de départ n'est pas évidente . On fait des chemins reliant les pépites d'angle pouvant bouger aux lignes et colonnes susceptibles de les accueillir jusqu'à saturer le graphe ( chaque arête doit être utilisée une fois et une seule ) . Après on alimente les lignes et les colonnes en utilisant les chemins mais c'est une autre affaire : la construction des chemins est-elle claire ?

Un exemple avec une grille 12X12 : Il y a 29 pépites susceptibles de bouger , 3 lignes et 5 colonnes pour les accueillir ( les nombres indiquent l'excédent ou le déficit dans la progression ligne par ligne ou colonne par colonne ) . Quels chemins pour illustrer cette configuration ?



@Nodgim : Un peu d'accord , j'ai des tas de problèmes qui me titillent depuis des années et que je ressors régulièrement , souvent pour pas grand chose , mais il m'arrive parfois d'avoir un flash . Il ne faut pas viser trop haut , juste un peu plus haut que ce qu'on sait faire .

Vasimolo

Oui, c'est clair J'ai compris ce qui, en général (pour tout gâteau) permet d'écrire quelque chose de similaire à ce que tu as écrit jusqu'à maintenant. J'attends de voir comment tu conclus.

Un détail : pourquoi avoir tracé C08 et C09 sur ton dessin ?

Récapitulons avant de donner la fin de la démonstration :

1°) On place les pépites dans les angles .

2°) Pour équilibrer la ligne [latex]k[/latex] on va selon les cas , monter [latex]\frac{h_k-b_{k+1}}{3}[/latex] pépites de la ligne [latex]k[/latex] à la ligne [latex]k+1[/latex] ou descendre [latex]\frac{b_{k+1}-h_k}{3}[/latex] pépites de la ligne [latex]k+1[/latex] à la ligne [latex]k[/latex] . Pour réaliser cet équilibre on a au moins trois pièces à notre disposition pour chaque déplacement .

3°) Même chose avec les colonnes en remplaçant bas et haut par gauche et droite .

4°) On relie les pépites qu'on peut déplacer pour réaliser les équilibres souhaités en 2°) et 3°) aux lignes et colonnes pouvant les accueillir .

5°) On ne touche pas aux arêtes des cases de degré 1 ( un seul voisin ) .

6°) On partitionne l'ensemble des arêtes restantes en chemins maximaux commençant et finissant par une ligne ou une colonne ( on passe une seule fois par chaque arête ) .

Maintenant , comment finir ?

On conserve chaque arête du 5°) et on supprime alternativement une arête sur deux des chemins définis en 6°) . Chaque case d'angle du graphe est alors reliée à une unique ligne ou colonne et on autorisera uniquement les déplacements de ces cases vers ces lignes ou colonnes . On avait initialement un surplus de pièces à disposition pour réaliser les deux équilibres mais certains conflits pouvaient apparaître : reste-t-il assez de liens pour satisfaire les deux ?

La réponse est clairement oui .

On avait au moins trois fois trop de pièces pour équilibrer chaque ligne ou chaque colonne . Ces lignes ou colonnes ne perdent aucune liaison si elles sont reliées à des cases d'ordre un , elle perde une liaison sur deux si elle figurent à l'intérieur d'un chemin et brutalement une liaison si elles figurent à la mauvaise extrémité d'un parcours . Heureusement elles ne peuvent pas figurer à plus d'une extrémité d'un chemin : il reste donc un nombre suffisant de cases d'angle permettant d'équilibrer les lignes et les colonnes .

Il n'y a plus qu'à choisir les pièces que l'on veut pour réaliser l'équilibre .

Vasimolo

Non, non, attends, je n'ai pas dit que je ne comprenais pas. J'étais parti faire du bois.

D'ailleurs, j'ai compris Le truc principal qui m'avait échappé, c'est quand tu dis : "pour réaliser cet équilibre on a au moins trois pièces à notre disposition pour chaque déplacement". C'est bien vu, et c'est très utile dans la suite, car dans ton graphe biparti, si une ligne (ou colonne) est de degré d, alors la partition du graphe en chemins puis la conservation d'une arête sur deux permettent de conserver au moins E(d/2) pépites pour reboucher cette ligne. Ça plus les pépites de degré 1, ça suffit amplement à notre bonheur.

Bref, là, j'ai compris la totalité de ta preuve. Félicitations pour ce raisonnement, c'était pas du gâteau !

Pour la généralisation aux rectangles, il me semble que ta preuve fonctionne telle qu'elle, non ?

J'ai un problème du même style sous le coude, d'énoncé très simple et de preuve très dure, à ceci près que j'ai trouvé une démonstration (qui n'utilise pas non plus de connaissance mathématique avancée). J'avais envie de le proposer, au cas où quelqu'un trouve une preuve élémentaire, on ne sait jamais. Mais j'hésite, car c'est un cadeau empoisonné. J'ai dû y passer 2 mois avant d'y arriver...