Devinette mathématique

[invite51d17075]

A propose max(B,C)+1
B propose max(A,C)+1
C propose max(A,B)+1

excellent, je dirais qu'il n'y a pas de solution, en un temps fini.

mais dans la pratique, ils peuvent devenir cinglés, ou s'entretuer.
et seul le dernier survivant gagne.
-----

[invite51d17075]

@ Goel :
si j'ai pu sembler agacé, c'est en partie du aux ambiguïtés dans les réponses ou dans l'interprétation de l'énoncé ( que j'ai cru ressentir ).
cela dit, "l énigme" a entrainé des considérations forts intéressantes ( grâce aux interventions de Médiat et de Schrodie-Cat ) et aurait méritée d'être proposée comme réflexion en mathématique du sup, et non en forum ludique.
c'est peut être une des raisons qui a amenée certains intervenants à réagir de la sorte.
cordialement.

il n'y a en fait de ludique que le jeu de mot entre "arbre" et TREE !

[Médiat]

Bonjour,

Je prends M(b+1) ou b est le nombre maximal de symboles qu'on puisse écrire sur le papier dont on dispose

L'écriture de cet algorithme va nécessiter d'écrire plus que b symboles, vous n'aurez donc pas la place pour les écrire.

Je précise pour les autres lecteurs (car vous semblez ne pas être tombé dans le piège), qu'il y a une différence colossale entre "pour tout n définir M(n)" et "définir pour tout n, M(n)".

[invite82078308]

Comme je l'ai remarqué, ma fonction M n'est pas définie par un algorithme.
J'en ai donné une courte définition.
La définir formellement serait plus long mais raisonnable.
Écrire b demande log₂(b) symboles.

[Médiat]

Si elle n'a pas de définition autre que par des mots, il suffit de définir la fonction constante égale à un nombre plus grand que tout nombre que les deux autres peuvent imaginer avec les moyens dont ils disposent.

[invite51d17075]

Si elle n'a pas de définition autre que par des mots, il suffit de définir la fonction constante égale à un nombre plus grand que tout nombre que les deux autres peuvent imaginer avec les moyens dont ils disposent.

cela rejoint un peu la remarque humoristique précédente de Deedee.

[Médiat]

Ou mon message #18

[invite82078308]

Si elle n'a pas de définition autre que par des mots, il suffit de définir la fonction constante égale à un nombre plus grand que tout nombre que les deux autres peuvent imaginer avec les moyens dont ils disposent.

Ce n'est pas une définition mathématique (notre candidat est mathématicien).
Je ne prétends pas que le nombre que j'ai défini (sans donner un moyen effectif de le calculer) soit imbattable, mais il fait mieux que toute définition au moyen exclusivement de fonctions calculables.

[Médiat]

Ce n'est pas une définition mathématique.

La votre non plus, ou alors quelque chose m'échappe :

Soit vous devez écrire la définition de M(n) (et je ne vois pas comment), soit celle de M(b+1) et vous n'aurez pas la place (et dans ce cas, b+1 suffit à battre b)

[invite51d17075]

Ou mon message #18

exact, je n'étais pas remonté assez haut.

[invite82078308]

La votre non plus, ou alors quelque chose m'échappe :

Soit vous devez écrire la définition de M(n) (et je ne vois pas comment), soit celle de M(b+1) et vous n'aurez pas la place (et dans ce cas, b+1 suffit à battre b)

J'ai donné une définition de M, (je n'ai pas spécifié le langage de description d'algorithme que j'utilise, mais ce n'est pas un problème), ce n'est pas une définition formelle, mais elle est formalisable, dans une théorie comme par exemple la théorie des ensemble qu'utilisent couramment les mathématiciens. Dans le formalisme pur et dur de ZF, ce serait plus laborieux.

[Médiat]

elle est formalisable, dans une théorie comme par exemple la théorie des ensemble qu'utilisent couramment les mathématiciens. Dans le formalisme pur et dur de ZF, ce serait plus laborieux.

Mon problème est là : je ne vois pas comment.

[invite82078308]

Là, il faut être familiarisé avec la théorie de Turing.
J'ai utilisé principalement la notion d'algorithme, celle-ci a été formalisée entre autres par Allan Turing.

[invite82078308]

J'ai utilisé la notion de longueur d'un algorithme.
Dans le cadre du formalisme des machines de Turing, un algorithme sera représenté par une suite finie de symboles sur une bande de la machine, on peut donc parler de la longueur de cet algorithme.

[Médiat]

J'entends bien, mais je ne vois toujours pas.

Vous avez écrit : "

dans une théorie comme par exemple la théorie des ensemble qu'utilisent couramment les mathématiciens. Dans le formalisme pur et dur de ZF, ce serait plus laborieux.

", je serais particulièrement content de voir cela dans le langage de ZFC

[Médiat]

Dans le cadre du formalisme des machines de Turing, un algorithme sera représenté par une suite finie de symboles sur une bande de la machine, on peut donc parler de la longueur de cet algorithme.

Comment faites vous ????? En particulier pour les algorithmes de longueur inférieurs à b que vous ne pouvez déjà pas écrire

[invite82078308]

Je ne peux pas les écrire tous, mais je peux les décrire, je définit l'ensemble des suites de symboles de longueur inférieure à b , qui constituent autant d'algorithmes. Parmi ces algorithmes, certains fonctionnent et donnent un résultat, d'autre sont erronés et ne terminent jamais. J'aurais du préciser que je ne considère que le algorithmes qui terminent dans ma définition de M.
C'est une définition mathématique, mais ce n'est pas une définition récursive du fait du théorème d'indécidabilité de l'arrêt de Turing.

[Deedee81]

Salut,

On peut effectivement définir un nombre qu'on ne peut pas explicitement calculer. J'avais déjà vu des exemples (justement dans des articles sur la calculabilité, dont un de Delahaye).

Mais tout ça n'empêche pas un autre (disons le physicien) d'inscrire "réponse du mathématicien + 1".
Dans tous les cas, il gagne. Et vis à vis de l'énigme, ça, ça me gêne.

[invite82078308]

En fait, il faut préciser les règles du jeu.
Je reviens à mon idée de compétition entre mathématiciens, qui devront donc écrire leurs réponses dans une théorie spécifiée à l'avance.
Dans ce cas, la divination (utiliser ce que répondront les autres) n'est pas autorisée.
Si la théorie est tant soit peu puissante, le problème n'est pas trivial.

[Deedee81]

Dans ce cas, la divination (utiliser ce que répondront les autres) n'est pas autorisée.

Mais quelle que soit la solution que tu envisages pour le mathématicien. Qu'est-ce qui empêche de dire que le physicien a aussi pensé à cette solution en ajoutant "+1".
Je persiste à dire que l'énigme est mal posée.

Mais par contre cette histoire de "grand nombre définissable bien que non calculable" n'est pas inintéressante.

[invite82078308]

Mais quelle que soit la solution que tu envisages pour le mathématicien. Qu'est-ce qui empêche de dire que le physicien a aussi pensé à cette solution en ajoutant "+1".
Je persiste à dire que l'énigme est mal posée.
(...)

"Cette solution" ne vas pas, il faut <copie de la solution> + 1 .
Et si il ne reste plus de place pour le "+1" sur le papier ?

[Médiat]

Je ne peux pas les écrire tous, mais je peux les décrire

Donc pas formalisable contrairement à ce que vous disiez.

Tant que ce ne sont que des mots, et non des mathématiques ...

La charge de la preuve vous revenant, moi j'en reste là, tant que je ne l'ai pas vue.

[invite82078308]

On peut définir un ensemble autrement qu'en énumérant ses éléments.

[Médiat]

Faites !

[invite82078308]

Cela a déjà été fait.

[invite82078308]

Considérons l'ensemble des parties de {1,2,3,4,5,6,7,8,9,10,11,,12,1 3,14,15,16,17,18,19,20}
ce nest pas une définition pour vous? ou alors définissez le, ou alors prétendez qu'on ne peut pas le définir.

[Deedee81]

Et si il ne reste plus de place pour le "+1" sur le papier ?

Ah oui, bien vu. Bien qu'il va alors être TRES difficile de trouver la réponse (*). C'est plus un challenge, c'est carrément le championnat galactique

(*) A la question "quelle est le plus grand nombre définissable (**) en N (***) caractères"
(**) Après avoir fixé les règles utilisables.
(***) en fait la question est extrêmement difficile si on fixe N, par exemple pour 100. Mais je ne suis même pas sûr qu'il y ait une réponse pour N quelconque. J'ai l'intuition que la réponse avec N quelconque est.... indéfinissable.

[invite82078308]

Pour N très petit, c'est jouable (il faut préciser dans quelle théorie), mais au-delà ...

[Médiat]

Considérons l'ensemble des parties de {1,2,3,4,5,6,7,8,9,10,11,,12,1 3,14,15,16,17,18,19,20}
ce nest pas une définition pour vous? ou alors définissez le, ou alors prétendez qu'on ne peut pas le définir.

1) C'est à vous de le faire (rappel : l'axiome dit que cet ensemble existe, il ne dit pas ce qu'il est (relisez cet axiome, vous verrez), même si dans le cas fini, c'est simple (mais foutrement long), à condition de l'écrire !)
2) Si vous voulez le faire pour n = b, vous n'aurez pas la place, par définition
3) Le problème c'est de le faire pour tout n

Finalement, j'ai peur que vous ne vous soyez fait abusé par la différence entre "pour tout n démontrer f(n)" et "démontrer pour tout n f(n)"

Je répète, la charge de la preuve vous reviens, si je la vois passer, je la saluerai, sinon je ne serai pas convaincu.

[invite82078308]

Notre mathématicien se réserve le droit d'utiliser toutes les ressources de ZFC (par exemple)pour démontrer des énoncés et définir des nombres.
J'ai l'impression que vous n’acceptez que les mathématiques de celui que j'ai appelé le comptable.