Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #26 - 04-05-2013 13:05:11

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Partage dun gâteau

Des gâteaux à masse négative smile

Restons sur le problème donné .

Vasimolo

#0 Pub

 #27 - 04-05-2013 14:01:38

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1374
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,464E+3

Partage d''un gâteau

Merci nodgim lol

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

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 : 1746

Partage d'u 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 : 639

Partage 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 : 4733

aPrtage d'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 : 2953

partage d'un fâ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 : 1746

Partage d'nu 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 : 4733

artage d'un gâ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

Vasimolo

 #35 - 07-05-2013 23:42:49

Tofic
Passionné de Prise2Tete
Enigmes résolues : 29
Messages : 72

partage d'in gâteau

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,464E+3

Partge d'un gâteau

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

Partage d'u 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 : 1945
Lieu: Paris

Partage dd'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

Partage d'uun gâteau

Ok, ça m'apprendra à bien lire hmm

 #40 - 08-05-2013 12:39:36

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,464E+3

Partage d'n 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 : 1746

Partage d'un gâteaau

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

Patrage d'un gâ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

 #43 - 11-05-2013 11:25:53

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

partage f'un gâteau

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,464E+3

pzrtage d'un gâteau

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 : 4733

partage d'un gâteay

Ces histoires de 0 sont un peu nulles lollol

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 : 2953

oartage d'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 : 4733

Partgae d'un 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 : 1945
Lieu: Paris

Partage 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

Partaeg d'un gâteau

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

-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 wink ) 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 tongue )

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
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 wink )
Il faut dire que le problème n'est pas facile à formaliser clairement.

Bonne prise de tête smile


Il y a sûrement plus simple.

 #50 - 12-05-2013 10:14:10

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

partagr 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.

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
P2T
Gâteau 100 par Vasimolo
27-06-2015 Enigmes Mathématiques
P2T
Partage de pirates par gonzague
20-07-2009 Enigmes Mathématiques
P2T
Gâteau 45 par Vasimolo
19-11-2011 Enigmes Mathématiques
P2T
Gâteau 14 par Vasimolo
14-07-2010 Enigmes Mathématiques
P2T
Gâteau 76 par Vasimolo
20-04-2014 Enigmes Mathématiques
P2T
Gâteau 60 par Vasimolo
08-06-2013 Enigmes Mathématiques
P2T
Gâteau 93 par Vasimolo
14-02-2015 Enigmes Mathématiques
P2T
Gâteau 99 par Vasimolo
13-06-2015 Enigmes Mathématiques
P2T
Gâteau 69 par Vasimolo
02-02-2014 Enigmes Mathématiques
P2T
Gâteau 126 par Vasimolo
01-09-2016 Enigmes Mathématiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete