énigme solitaire

[invitec314d025]

Ah oui !
Tout s'éclaire. C'est vraiment très très beau.
Même si je trouve ça beau parce que je n'aurai jamais pu trouver cela seul. Y a quand même des gens qui ont de ces intuitions...

Ce genre de fonctions a été nommé "fonctions pagodes". Je tiens le problème d'un vieux "pour la science" (début des années 90 je crois).
-----

[invite35452583]

Salut Matthias, (et aux autres)
hier soir j'ai été un peu déçu que tu mettes aussi rapidement la solution car malgré (et même grâce) à mon erreur initiale j'avais trouvé la démo.Ce n'est pas bien grave et de toute façon et surtout merci pour ce très joli problème.
Je reviens dessus car je ne suis pas d'accord avec le fait que la résolution de ce problème est entendue comme non intuitif ou non naturelle. Quelque part oui. Mais ce n'est pas vrai au regard de ce que nous a appris le développement récent des mathématiques, à savoir la "puissance" du changement de cadre. En particulier l'attribution de quantité numérique ou de structures algébriques à des situations géométriques ou topolgiques...(L'inverse est vrai aussi)
Un premier grand pas a été la géométrie cartésienne.
C'est le cas de toute la topologie algébrique.
La résolution du problème des 7 ponts (de ??) en est un bon exemple
En topologie générale, c'est par exemple la distance d'un point à une frontière (donc fermée) qui permet d'assurer des composantes connexes ouvertes dans de nombreux cas.
La théorie de Galois en est un autre exemple avec ces extensions, comme par exemple la théorie de Galois différentielle.
La démonstration du "dernier théorème de Fermat" est un exemple de changement de cadre (il y en 5 ou 6 "navettes" entre l'arithmétique, des variétés géométriques algébriques, des invariants purement algébriques...)
Dans ce problème, avoir l'idée d'attribuer une quantité numérique est assez naturelle (je ne suis d'ailleurs pas le seul à y avoir pensé, cf; post de Martini_bird). Quant à trouver lequel, je suis certainement avantagé par ma formation en topologie algébrique où la question première est souvent : quel est le bon "ingérdient" numérique ou algébrique?
Ici, il s'agissait de trouver une quantité numérique (je l'ai appelé potentiel au lieu d'évaluation, c'est pareil) qui:
* diminue ou reste constant à chaque mouvement (là mon erreur m'a aidé : tiens quand on avance un pion vers la case voulue on doit )vider des case plus éloignées mais il y en a deux).
* qui puisse prendre en compte un nombre dénombrable de cases et pions =>somme ou produit s'y prêtent bien, préférence somme plus manipulable et le produit risque d'aboutir de toute façon à une somme d'exposants.
Comme à une distance donnée le nombre de cases augmentant arithmétiquement mieux vaut utiliser les exponentielles (k^(-N) N étant la distance en cases) que les puissances (1/(N+1)^k)
Après avoir essayé les inverses de e ou 2, qui ne faisait pas diminuer la résolution de l'inégalité -k^(-N-2)-k^(-N-1)+k^(-N) négatif, le nombre d'or sortant on n'a peu de doute sur ce qu'il faut utiliser pour k.
Ca se calcule assez bien et on découvre que l'ordonné 5 est juste pour la limite (potentiel théorique au départ=1, un pion en ordonnée 5 potentiel=1, les deux étant en fait non des égalités mais des inégalités dans le bon sens : on ne peut pas utiliser tout le potentiel (nombre fini de coups donc pions non utilisés) et il ne peut pas y avoir simplement un pion en ordonnée 5 il en reste toujours même très éloignés.
Nos aïeux qui ont pensé à faire ce type de "changement de cadre" ont vraiment eu du génie mais c'est désormais assez banal.(*)
Un autre exemple où un changement de cadres permet de montrer une impossibilité : les dés pipés.

Cordialement

PS : ce qui ne veut pas dire que pour certains problèmes cela reste très difficile comme par exemple les noeuds.

[invite986312212]

La résolution du problème des 7 ponts (de ??) en est un bon exemple

Königsberg? Il y a une démonstration algébrique? celle que je connais est élémentaire. Elle revient à decouper le graphe en cycles et à raisonner par récurrence sur le nombre de cycles.

[invite986312212]

au fait pour l'énigme, le difficile était de deviner la solution, et la solution est jolie en effet. Pour ma part je croyais à la progression infinie. La démonstration évoque un peu (un aspect de) celle du théorème des quatre couleurs. On y définit une fonction de l'ensemble des sommets d'un graphe planaire dans Z et on fait ensuite des manipulations sur les arêtes qui changent ou laissent invariante la somme de la fonction.

[invitec314d025]

Salut Matthias, (et aux autres)
hier soir j'ai été un peu déçu que tu mettes aussi rapidement la solution car malgré (et même grâce) à mon erreur initiale j'avais trouvé la démo.

Désolé, j'aurais pu essayer de donner des indices avant de donner la solution.

Je reviens dessus car je ne suis pas d'accord avec le fait que la résolution de ce problème est entendue comme non intuitif ou non naturelle.

Oui, mais tu es très fort et très savant
Quant au fait d'associer une valeur numérique, oui je suis d'accord que c'est assez naturel. Chercher des invariants par exemple est souvent une méthode efficace (genre la signature dans les nombreux jeus faisant intervenir des permutations).
C'est surtout la manière dont j'ai balancé la fonction toute faite qui fait apparaître le problème comme non intuitif.

J'aurais pu commencer avec le même genre de problème, mais sur un plateau normal, en demandant de montrer qu'on ne peut pas passer d'une situation simple donnée à une autre, mais je n'ai pas résisté à montrer directement ce résultat que je trouve magnifique (si quelqu'un a envie de créer des problèmes de ce genre, ça peut être sympa).

[invite35452583]

Königsberg? Il y a une démonstration algébrique? celle que je connais est élémentaire. Elle revient à decouper le graphe en cycles et à raisonner par récurrence sur le nombre de cycles.

Rapidement car je ne me rappelle plus des valeurs mais on peut montrer l'impossibilité en attribuant à chaque "zone" un nombre, les passages des ponts (n) augmente ou diminue d'une certaine valeur (v_n). Et on montre (plutôt on constate) qu'aucune somme des (+ ou -) v_n ne convient.

Cordialement

[invite35452583]

Quant au fait d'associer une valeur numérique, oui je suis d'accord que c'est assez naturel. Chercher des invariants par exemple est souvent une méthode efficace (genre la signature dans les nombreux jeus faisant intervenir des permutations).
C'est surtout la manière dont j'ai balancé la fonction toute faite qui fait apparaître le problème comme non intuitif.

Oui, si celle-ci n'est pas évidente elle est assez "naturelle" (oui je sais il faut un peu d'expérience dans ce genre de manip) une fois qu'on s'est convaincu empiriquement du résultat (remarque moi je l'étais par Yat et par suite de ta confirmation , je suis plutôt mauvais en manipulation de pions ou ce genre de choses).

Cordialement

PS : la proposition de créer ce type de problèmes peut en effet être sympa (mais la création, ce n'est pas mon fort) Je me suis demandé si on pouvait définir une sorte de coups dénombrable arrivant à placer un pion en 5 mais je n'ai pour l'instant qu'une définition "sommaire" qui finit par remplir le plan.

[invitec314d025]

Je me suis demandé si on pouvait définir une sorte de coups dénombrable arrivant à placer un pion en 5 mais je n'ai pour l'instant qu'une définition "sommaire" qui finit par remplir le plan.

Houla, tu veux faire ça en analyse non standard ?

[invite35452583]

Houla, tu veux faire ça en analyse non standard ?

Non pas vraiment.
Voilà l'idée de "mon extension"
un coup élémentaire est :
je prends un pion d'une case a
je saute au-dessus d'une case b dont je retire le pion
j'arrive sur une case c qui gagne donc un pion.
a,b et c étant trois cases contiguës.
Bilan : -1 pour a et b, +1 pour c.
Un "coup dénombrable" est une famille dénombrable de tels coups telle que :
pour chaque case le nombre de coups (que ce soit en position a, b ou c) dans laquelle elle est impliquée est fini.
Le bilan d'une case= nombre de pions au départ-nombre de fois en a-nombre de fois en b+nombre de fois en c.
La famille n'est acceptée que si le bilan de chaque case vaut 0 (vide) ou 1 (un pion).
Or, et c'est même assez facile de se rendre compte qu'avec cette extension presque toute est permis (un même coup élémentaire peut être pris plusieurs fois). D'où recherche d'une contrainte supplémentaire pour laquelle un pion en 5 est possible (mais pas en 6). La contrainte chaque coup élémentaire revient au cas fini (si je ne me suis pas trompé ) donc ne convient pas. Imposer un ordre d'"éxécution des coups" dans la famille aussi.
C'est évidemment le fait que n=5 soit aussi limite (évaluation totale théorique au départ=1=évaluation (un pion unique en 5) que j'essaie d'illustrer.

[invitec314d025]

Sinon, on peut essayer le même problème que précédemment, mais en ne partant qu'avec un quart de plan vide (ou même juste un carré vide au milieu d'une mer de pions).

[invite35452583]

Sinon, on peut essayer le même problème que précédemment, mais en ne partant qu'avec un quart de plan vide (ou même juste un carré vide au milieu d'une mer de pions).

J'ai regardé le quart de plan plein (j'avais du mal lire ), c'est joli aussi avec une belle diagonale séparant la zone des cases atteignables et non atteignables. Je suppose qu'on retrouve une diagonale de ce type avec le quart vide.
C'est vrai que c'est joli et efficace ces fonctions pagodes.

[invite986312212]

Rapidement car je ne me rappelle plus des valeurs mais on peut montrer l'impossibilité en attribuant à chaque "zone" un nombre, les passages des ponts (n) augmente ou diminue d'une certaine valeur (v_n). Et on montre (plutôt on constate) qu'aucune somme des (+ ou -) v_n ne convient.

oui, ça doit être simplement le degré (= nombre de ponts) du sommet (= zone). A chaque fois qu'on passe par une zone on "efface" deux ponts et on décrémente donc le degré de 2. Comme à la fin tous les degrés doivent être zéro, on montre qu'une condition nécessaire est que tous les degrés soient pairs (sauf peut-être ceux de 2 sommets, si on n'impose pas de revenir à son point de départ). La partie intéressante du théorème est la réciproque: il suffit que chaque sommet soit de degré pair pour qu'il existe un parcours eulérien.

[invitec314d025]

Dans le même genre mais en plus simple.
Est-ce que ceci est possible ?

[yat]

Dans le même genre mais en plus simple.
Est-ce que ceci est possible ?

Pas de news sur celui-là ?

[invitec314d025]

Pas de news sur celui-là ?

Je n'ai pas précisé : ce n'est pas un problème ouvert et il n'est pas de moi.
Tu as essayé ?

[yat]

Tu as essayé ?

Oui, et je n'ai pas réussi... mais comme j'ai toujours été une bille à ce jeu, de là à dire que c'est impossible il reste un grand pas. Par contre j'ai un peu tatonné pour voir s'il y avait une méthode un peu similaire à l'autre pour démontrer que ce n'est pas possible, mais je n'aboutis pas.

En bref, je sèche

[invitec314d025]

Bon, c'est effectivement impossible, et on peut le montrer à l'aide d'une fonction pagode bien choisie.

[yat]

Hmm...

J'ai cherché à reproduire une fonction comme celle de l'énigme précédente. C'est à dire, la case du milieu vaut ⁰, les quatre voisines ¹, et ainsi de suite... ça ne marche pas, la somme des cases occupées au début est bien supérieure à la somme des cases occupées à la fin. Par contre je ne vois pas trop comment placer les billes différemment, puisqu'il faut garder une fonction telle qu'un coup ne permette pas d'augmenter la valeur totale. Du coup si je veux attribuer une valeur maximale aux cinq billes du centre et minimale au reste, je suis obligé de faire comme ça mais ça n'est pas suffisant...

J'ai essayé aussi de numéroter avec des entiers, mais je n'y arrive pas non plus.

[yat]

ahhhh... quel boulet !

Les nombres négatifs, bien sur... comment n'y ai-je pas pensé plus tôt ?

Bon, je mets des -1 dans les coins, des 1 dans chacune des cases qui les touchent directement, et des 1 dans les cases de la croix. Sauf erreur, la décroissance est respectée, la croix vaut 5 alors que le reste ne vaut que 4.

J'ai bon ?

[invitec314d025]

Oui ça marche
C'est une solution parmi d'autres, celle que j'avais est à peine différente.
En fait vu que le plateau ne s'étend pas à l'infini, l'utilisation de puissances n'est pas vraiment justifié.