![](/img/vague-bas-gauche.png) |
#26 - 04-05-2013 13:05:11
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
Partage d'un gteau
Des gâteaux à masse négative ![smile](img/smilies/smile.png)
Restons sur le problème donné .
Vasimolo
#27 - 04-05-2013 14:01:38
- golgot59
- Elite de Prise2Tete
- Enigmes résolues : 48
- Messages : 1494
- Lieu: Coutiches
paryage d'un gâteau
Edit : Pardon, j'ai dit nimp !
#28 - 04-05-2013 14:12:10
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,952E+3
partzge d'un gâteau
Merci nodgim
Je me suis demandé comment tu arrivais à faire perdre : c'est simple , on peut toujours faire en sorte de faire perdre !
On part de ton exemple 1 : 1473829
Dans le meilleur des cas, le joueur qui prend gagne de 9+8+7+4 contre 1+2+3 , soit de 22 points.
Si je rajoute artificiellement -23, même le meilleur joueur du monde ne saura pas gagner en choisissant en premier car cela crée artificiellement un handicap de -23 pour ce joueur avec les mêmes écarts ... ![big_smile](img/smilies/big_smile.png)
C'est donc un faux problème de s'autoriser les nombres négatifs.
#29 - 05-05-2013 12:00:45
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Prtage d'un gâteau
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.
#30 - 05-05-2013 12:12:57
- godisdead
- Expert de Prise2Tete
- Enigmes résolues : 22
- Messages : 747
partagz d'un gâteau
Si je découpe comme ça ? 919191913
#31 - 05-05-2013 12:30:38
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
Partage 'un gâteau
Si je prends le 9 au centre , tu continues comment ?
Vasimolo
#32 - 06-05-2013 19:38:20
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Pratage d'un gâteau
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 deduire une solution sans 0.
Tu aurais donc une solution avec un nombre pair de parts ?
#33 - 06-05-2013 21:33:12
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
Parrtage d'un gâteau
Non, il n'y a pas de solution avec un nombre pair de parts.
#34 - 06-05-2013 23:22:04
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
Partage d'un ggâteau
Évidemment , le problème est de savoir s'il existe une solution avec un nombre impair de parts .
Je n'y crois pas mais j'attends ![smile](img/smilies/smile.png)
Vasimolo
#35 - 07-05-2013 23:42:49
- Tofic
- Passionné de Prise2Tete
- Enigmes résolues : 29
- Messages : 72
Partage d'un gâteua
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?
#36 - 08-05-2013 07:48:47
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,952E+3
partage d'un gâyeau
Une part "0" est une part de valeur négligeable par rapport aux autres je pense. En gros elle n'influe pas sur le total des joueurs (sauf si les autres "grosses parts" mènent à une égalité stricte) Si tu ne fais que des parts comme ça, elles ne sont plus négligeables les unes par rapport aux autres.
#37 - 08-05-2013 11:57:59
- Tofic
- Passionné de Prise2Tete
- Enigmes résolues : 29
- Messages : 72
partafe d'un gâteau
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.
#38 - 08-05-2013 12:03:25
- SabanSuresh
- Elite de Prise2Tete
- Enigmes résolues : 45
- Messages : 1951
- Lieu: Paris
Partag ed'un gâteau
Oui mais là personne ne gagne et on veut que le découpeur gagne à coup sûr.
#39 - 08-05-2013 12:15:54
- Tofic
- Passionné de Prise2Tete
- Enigmes résolues : 29
- Messages : 72
Parrtage d'un gâteau
Ok, ça m'apprendra à bien lire ![hmm](img/smilies/hmm.png)
#40 - 08-05-2013 12:39:36
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,952E+3
Partaeg d'un gâteau
Ce n'est pas ce que je voulais dire Tofic :
En prenant des parts (au hasard) 6 9 7 2 5 8 7 0,000001
Le 0,000001 est négligeable par rapport à l'ensemble. (sauf si l'ensemble mène vers une stricte égalité)
Par contre 0,000001 0,000001 0,000002 0,000002 0,000001 revient à 11221, on ne peut plus considérer cette part comme négligeable.
Dans le premier cas elle représente 0,000002 % du gâteau et dans le second 15 %.
Là où je ne rejoins pas le raccourci de titoufred, c'est qu'il assimile ça à 0 et néglige le cas d'une égalité sur les autres parts.
#41 - 09-05-2013 14:48:43
- titoufred
- Elite de Prise2Tete
- Enigmes résolues : 20
- Messages : 1749
partage f'un gâteau
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.
#42 - 11-05-2013 01:50:11
- Tofic
- Passionné de Prise2Tete
- Enigmes résolues : 29
- Messages : 72
Partage d'un âteau
Le 0,000001 est négligeable par rapport à l'ensemble. (sauf si l'ensemble mène vers une stricte égalité)... Là où je ne rejoins pas le raccourci de titoufred, c'est qu'il assimile ça à 0 et néglige le cas d'une égalité sur les autres parts.
C'est bien ça le problème, soit la part"o" vaut bien 0 soit elle a quand même une valeur qui doit être prise en compte.
Gwen, si je comprends bien, la part "0" n'est pas rien en quantité, ce sont des miettes. Même si la quantité qu'elle représente est négligeable (peut même être considéré nulle), il n'en demeure pas moins que sans cette part le gâteau ne l'est plus. Le gâteau est pour toi la somme de ses parts en quantité et en valeur. Je sais qu'en math (et dans les énigmes), "les mots on leur importance", je n'ai sans doute pas appréhendé "négligeable" de la bonne façon.
Le raisonnement que je tiens avec le petit dessin ci-dessous où le choix initial n'importe pas, n'est pas correct non plus alors. D'autant qu'on se retrouve avec une solution exclue par titoufred (ex æquo).
![http://www.prise2tete.fr/upload/Tofic-gateau.png](http://www.prise2tete.fr/upload/Tofic-gateau.png)
#43 - 11-05-2013 11:25:53
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Partage d'un gâtea
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.
#44 - 11-05-2013 12:24:31
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,952E+3
Partage d'un gâtea
Si les zéros sont des miettes (toutes égales) on peut multiplier au lieu d'ajouter. Cela ne crée pas de différence mais permet de ramener les miettes à 1 , je pense.
#45 - 11-05-2013 12:26:20
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
partage d'yn gâteau
Ces histoires de 0 sont un peu nulles ![lol](img/smilies/lol.png) ![lol](img/smilies/lol.png)
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
#46 - 11-05-2013 14:01:19
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Partage dd'un gâteau
Ce n'est pas clair pour moi, cette histoire de transposition d'une solution avec des 0 vers une solution sans 0. Comment t'y prends tu, Vasimolo ?
#47 - 11-05-2013 15:11:46
- Vasimolo
- Le pâtissier
- Enigmes résolues : 49
- Messages : 5,418E+3
Partage dun gâteau
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
#48 - 11-05-2013 15:33:34
- SabanSuresh
- Elite de Prise2Tete
- Enigmes résolues : 45
- Messages : 1951
- Lieu: Paris
Partge d'un gâteau
Ah ouais, c'était pas non plus très clair pour moi. Mais en fait, c'est aussi compliqué de chercher une solution avec des parts strictement positives, car cela revient au même.
#49 - 11-05-2013 23:55:06
- cogito
- Expert de Prise2Tete
- Enigmes résolues : 48
- Messages : 593
Partage d'un gtâeau
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 ![smile](img/smilies/smile.png) 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 ![smile](img/smilies/smile.png)
Il y a sûrement plus simple.
#50 - 12-05-2013 10:14:10
- nodgim
- Elite de Prise2Tete
- Enigmes résolues : 0
- Messages : 3801
Partage d''un gâteau
Bon, je crois avoir la solution, et c'est bien Vasimolo qui avait raison. Revenons au cas élémentaire d'un nb pair de parts: le 1er qui joue peut choisir la parité du rang des parts, paire ou impaire, selon qu'il débute par un bout ou par l'autre. Si la somme est impaire, c'est donc facile pour lui de choisir la plus grosse somme; il gagne donc toujours. Il faut remarquer tout de même que, si le 1er joueur peut choisir la parité, le second joueur peut à son tour choisir l'autre parité, et s'y fixer jusqu'au bout: le second joueur n'est donc pas totalement passif: il peut maitriser sa perte, même s'il est sûr de perdre. C'est à dire qu'il pourra choisir une perte minimale s'il en a la possibilité. Pour un nombre impair de parts, prenons par exemple 9 parts. En ôtant 1 part, il en reste 8, qu'on peut mettre dans une balance, 4 d'un coté, 4 de l'autre, du fait que la parité peut toujours être maitrisée par l'un ou l'autre des joueurs, et surtout le second. Si le 1er joueur ôte la part 1, on peut répartir les parts dans la balance comme ceci: 2468--3579 Répartition 1: 1---2468---3579. En prenant la part 2 au lieu de 1, la répartition devient: 2---1468---3579 Toutes les répartitions possibles selon la part ôtée en 1er: 1---2468---3579 2---1468---3579 3---1468---2579 4---1368---2579 5---1368---2479 6---1358---2479 7---1358---2469 8---1357---2469 9---1357---2468
On remarque que, d'une répartition à la suivante, il y a échange d'une seule part à la fois, tantôt sur un plateau, tantôt sur l'autre. On remarque aussi que la balance ne peut pas être toujours plus lourde d'un seul coté pour toutes les répartitions, car insidieusement, les paires sont remplacés par des impaires, et vice versa. Supposons qu'en 5---1368---2479, 1368 est plus lourd, et qu'en 6---1358---2479, 1358 est plus léger. Si on remet 6 avec 1358, ça redevient évidemment plus lourd, et si on met 6 avec 2479, ça confirme que 2479 est plus lourd. Dans tous les cas, 6 fait la différence. En prenant la part 6, et en respectant la parité opposée du 2er joueur, le 1er joueur gagne à tous les coups.
Mots clés des moteurs de recherche
|
![](/img/vague-haut-droite.png) |