Edit : Pardon, j'ai dit nimp !

Effectivement, les parts negatives sont prohibees. On peut en revanche s'autoriser des parts a 0 (des miettes), car si l'on trouve une solution avec des 0, on peut facilement en deduire une solution sans 0.

Si je prends le 9 au centre , tu continues comment ?

Vasimolo

Non, il n'y a pas de solution avec un nombre pair de parts.

Salut,

titoufred a écrit:

Effectivement, les parts negatives sont prohibees. On peut en revanche s'autoriser des parts a 0 (des miettes), car si l'on trouve une solution avec des 0, on peut facilement en déduire une solution sans 0.

Ca parait absurde de ne faire que des parts 0, mais avec cette configuration, le coupeur est sûr de ne pas perdre.
A moins que les miettes évoquées aient une valeur pour les joueurs?

Salut Gwen, si je comprends ce que tu dis, 1 part"0" est négligeable mais n parts "0" ne l'est plus?


Je pensais à une config comme celle-ci: 000 par exemple.

Ok, ça m'apprendra à bien lire

Je disais juste que l'on peut s'autoriser des parts à 0 (pas toutes à 0 bien sûr) pour chercher un découpage gagnant, car si l'on trouve un découpage gagnant avec des 0, alors on peut facilement en déduire un découpage gagnant sans 0.

Titoufred a clairement écrit que la transposition d'une solution avec des zéros vers une solution sans 0 était faisable, donc ce n'est pas la peine de s'escrimer à chipoter sur un presque zéro. Ce qui me trouble, c'est sa façon de transposer la solution avec 0 vers une solution sans 0 avec un nombre impair de parts... D'où ma remarque précédente qui n'a peut être pas été bien comprise.

Ces histoires de 0 sont un peu nulles

Il est clair que si on trouve une solution strictement gagnante pour le découpeur avec des parts nulles , on aura une découpe gagnante avec des parts non nulles .

Je doute énormément de l'existence d'une telle découpe et si quelqu'un en a une j'aimerais bien la voir .

Je chercherais plutôt une preuve que le découpeur peut au mieux égaliser mais ça n'a pas l'air simple .

Vasimolo

C'est assez simple , imagine que le découpeur gagne en faisant n parts dont m nulles . Si il note g le gain minimal qu'il va réaliser , il peut alors ajouter g/(m+1) à chaque part nulle du gâteau et il gagnera encore forcément d'au moins g/(m+1) à la fin du partage .

Vasimolo

Bonjour à tous, cela fait plusieurs jours que je suis cette discussions,
je pense avoir enfin trouver une preuve
(bien qu'elle doit comporter encore quelques trous )

-Pour le cas où le nombre de parts est pair, tous le monde est d'accord.

-Pour le cas où le nombre de parts est impair, je vais d'abord essayer
d'expliquer le principe sur un exemple simple avec un gâteau à trois parts :

Soit [latex]a,b,c[/latex] le poids (positif ) de chacune des parts.
Le joueur qui découpe aura une part et celui qui choisit en aura deux.

Le joueur qui découpe veut donc trouver une valeurs des trois nombres [latex]a,b,c[/latex] pour que les trois inégalité suivantes soit vérifier :
[TeX]a+b<c[/TeX]
[TeX]b+c<a[/TeX]
[TeX]c+a<b[/TeX]
Or ceci est impossible.
Spoiler : [Afficher le message] 
En effet, si on ajoute [latex]a[/latex] de chaque coté de la troisième inégalité par
exemple on obtient [latex]c+2a<b+a[/latex], et donc d'après la première
inégalité on aurait [latex]c +2a < c[/latex] ce qui est absurde (c'est là qu'intervient la positivité).


En fait une seul de ces trois inégalité est vérifié.
Le joueur qui choisi fait en sorte de ne pas se trouver dans ce cas là.
Remarque : si deux seulement de ces inégalités était vérifiées alors le joueur
qui découpe gagnerait.

Le problème du partage du gâteau est une généralisation du résultat ci-dessus,
mais avec un nombre impair quelconque de nombres positifs.

Soit donc [latex]k[/latex] un entier tel que [latex]2*k+1[/latex] soit le nombre de parts du gâteau.
Soit [latex]p_1,p_2,\ldots,p_{2k+1}[/latex] le poids de chacune des parts du gâteau.

La stratégie du joueur qui choisit va être (en plus de devoir choisir la bonne
première part) de faire en sorte que le joueur qui découpe ne puisse jamais
prendre deux parts consécutives (comme le gâteau est rond [latex]p_1[/latex] et [latex]p_{2k+1}[/latex]
sont des parts consécutives, je fais la remarque parceque plus loin quand je parlerais d'ensembles d'indices consécutifs je considérerais que [latex]1[/latex] et [latex]2k+1[/latex] sont consécutifs.)

Comme pour le cas à trois parts, on cherche toutes les inégalités possibles
qui puisse être favorables au joueur qui découpe.

On cherche donc des ensembles [latex]C[/latex] (pour choisir) et [latex]D[/latex] (pour découper) de tels
sorte que :
i) [latex]|C| = k + 1[/latex]
ii) [latex]|D| = k[/latex]

iii)[latex]C[/latex] et [latex]D[/latex] forment une partition de l'ensemble [latex]\{1,\ldots,2k+1\}[/latex]

iv)[latex]D[/latex] ne contient aucun nombre consécutif (dans le sens expliqué plus haut)

v)[latex]\sum_{i\in C}p_i<\sum_{i\in D}p_i[/latex]

Théorème 1 : le nombre d'ensemles vérifiants ii) et iv) est 2k+1.
Preuve :
Spoiler : [Afficher le message]
Imaginez que vous ayez [latex]2k+1[/latex] tiroirs, vous voulez remplir [latex]k[/latex] tiroirs de tels sorte que deux tiroirs consécutifs ne soit jamais pleins.
Vous aver donc 1 tiroir plein toujours suivi d'un tiroir vide, donc
donc pour [latex]k[/latex] tiroir pleins on a [latex]k[/latex] tiroirs vides, ce qui fait [latex]2k[/latex] tiroirs d'utilisé.
Il reste donc comme degré de liberté un tiroir vide et ce tiroir vide a 2k+1 places possibles.


Si celui qui découpe arrive à trouvé deux ensembles [latex]D1[/latex] et [latex]D2[/latex] disjoints qui vérifient les propriétés ci-dessus alors il a gagné.
Spoiler : [Afficher le message] En effet, si celui qui choisit  prend une première part dont l'indice est dans [latex]D1[/latex] alors le joueur qui découpe peut prendre les parts dans l'ensemble d'indices [latex]D2[/latex] et vice versa.

Théorème 2 : Il n'existe pas deux ensembles disjoints [latex]D1[/latex] et [latex]D2[/latex] comme ci-dessus.
Preuve:
Spoiler : [Afficher le message]
Supposons que de tels ensemble [latex]D1[/latex] et [latex]D2[/latex] existent, alors :

1- Comme [latex]D1[/latex] et [latex]D2[/latex] sont disjoints et de cardinal [latex]k[/latex], alors le cardinal de [latex]D1\cup D2[/latex]
est 2k, donc il existe un seul élément qui ne soit ni dans [latex]D1[/latex], ni dans [latex]D2[/latex].
Appelons cet élément [latex]j[/latex].

2- D'après ce qui précède, [latex]D1[/latex], [latex]D2[/latex], [latex]\{j\}[/latex] forme une partition de [latex]\{1,\ldots,2k+1\}[/latex]. Et donc d'après iii) :
[TeX]C1=D2\cup\{j\}[/latex] et [latex]C2=D1\cup\{j\}[/latex].

3- D'après v) et 2- on a les deux inégalités suivantes :

-[latex]\sum_{i\in D2\cup\{j\}}p_i<\sum_{i\in D1}p_i[/TeX]
-[latex]\sum_{i\in D1\cup\{j\}}p_i<\sum_{i\in D2}p_i[/latex]

ce qui peut se réécrire comme :

-[latex]\sum_{i\in D2}p_i+p_j<\sum_{i\in D1}p_i[/latex]

-[latex]\sum_{i\in D1}p_i+p_j<\sum_{i\in D2}p_i[/latex]

Si l'on pose [latex]c=\sum_{i\in D1}p_i[/latex],    [latex]a=p_j[/latex]   et  [latex]b=\sum_{i\in D2}p_i[/latex]    alors on obtient le même

système que pour le gateau à trois parts :
-[latex]b+a<c[/latex]
-[latex]c+a<b[/latex]

et donc par le même raisonnement on arrive à une absurdité.


En fait si on fait la liste de tous les ensembles [latex]D[/latex] qui sont favorables,
alors si l'intersection de tous ces ensembles est vide celui qui découpe gagne.
Sinon (celui qui choisit) choisit une part dans l'intersection de tous ces ensembles
(et fait en sorte que son adversaire ne prenne jamais deux parts consécutives)
et celui qui découpe n'a plus aucune chance de gagner.

Le Théorème 2 dit que deux (seulement) ensembles favorables d'intersection
vide n'existe pas. Mais peut-être que l'intersection avec d'autres ensembles favorables est vide ??

Mais en fait non (haha )

Théorème 3 : Si [latex]D1,\ldots,Dn[/latex] sont [latex]n[/latex] ensembles favorables (i.e vérifiant les conditions i) à v)) et d'intersection vide (avec [latex]2\le n[/latex]), alors
deux d'entre eux sont d'intersection vide. (hors le Théorème 2 dit que c'est impossible).

Preuve :
Spoiler : [Afficher le message]
C'est ici le passage un peu délicats
Il faux avoir en tête cette image de la preuve du Théorème 1 (avec les tiroirs).

Les ensembles d'indices seront des ensembles contentant des nombres
qui vont de deux en deux (pour pas être consécutifs) sauf éventuellement à un
endroit où il y aura un saut de trois (la case vide qui se ballade).
Ce saut de trois change la parité des éléments de l'ensemble.

Hum, bon d'accord essayons sur un exemple pour [latex]k=5[/latex]
(et donc [latex]2k+1 = 11[/latex]).

(Je suppose que les ensembles sont triés)

Un ensemble possibles est [latex]\{1,3,6,8,10\}[/latex]
on commence par des nombres impairs : 1 3, et ensuite nous avons que des nombres pairs : 6 8 10.

En fait nous avons cinq configurations possibles :

--Soit le premier élément de l'ensemble est 1 alors :
  1- L'ensemble ne contient que les nombres impairs jusqu'à 2k-1
         * (1 3 5 7 9) dans notre exemple.
  2- L'ensemble contient d'abord des nombres impairs et ensuite des nombres pairs
        *(1 3 6 8 10) dans notre exemple.

--Soit le premier élément de la liste est 2 alors :
  3- L'ensemble ne contient que les nombres pairs.
        *(2 4 6 8 10) dans notre exemple.
  4- L' ensemble contient d'abord des nombres pairs puits des nombres impairs.
        *(2 4 6 9 11) dans notre exemple.

--Soit le premier élément de la liste est 3 alors :
  5- L'ensemble ne contient que les nombres impairs jusqu'à 2k+1.
        *(3 5 7 9 11) est la seul possibilité dans notre exemple.

Pour résumé les cinq configuration nous avons  :

   1-  [latex]1 I I I I I I ... 2k-1[/latex]
   2-  [latex]1 I I I P P P ... 2k-2[/latex]
   3-  [latex]2 P P P P P P ... 2k-2[/latex]
   4-  [latex]2 P P P I I I ... 2k+1[/latex]
   5-  [latex]3 I I I I I I ... 2k+1[/latex]

avec I pour Impair et P pour Pair.

Là je ne sais pas trop expliquer cela (c'est le trou de la démonstration).
Disons que si on analyse tous les cas, pour avoir une intersection vide
il faut :
  -Soit un ensemble de type 1 avec un ensemble de type 3.
  -Soit un ensemble de type 5 avec un ensemble de type 3.
  -Soit un ensemble de type 2 avec un ensemble de type 4 pas tous.
  -Soit un ensemble de type 1 avec un ensemble de type 4 particulier.
  -Soit un ensemble de type 5 avec un ensemble de type 2 particulier.

Bref dans tous les cas on a l'intersection de 2 ensembles qui est vide.


Bon voilà, j'ai essayé d'expliquer le mieux que j'ai pu.
Je pense que j'en ai perdu certains, mais j'espère pas trop quand même
Je peut répondre à des questions si il y a des points vraiment pas très clairs
(il doit y en avoir, c'est sûr )
Il faut dire que le problème n'est pas facile à formaliser clairement.

Bonne prise de tête