Enigmes - Volume XVII

Si la portion P0 est "à midi" sur la pizza, si Bob choisi la portion à droite de P0, alors Alice récupèrera Pn qui est à gauche de P0.

Edit : je me plante...

@Insert : rien n'a en fait changé depuis ma prépa, je lis (très) mal les énoncés.
Oui il y a un nombre pair de portions.
Et ma compréhension n'est pas bonne puisque il n'y a pas de sens imposé.

Je pars me coucher.

@GoOodron Mais reviens hein, on aura besoin de toi

Allez, sans faire de savants calculs, juste par intuition :

Si le centre n'est au centre et qu'il y a un nombre paire donc, la moitié des parts sera plus importantes que l'autre moitié.

Pour me faire comprendre, disons qu'il y a 6 parts.
3 des parts côte à côte seront plus importantes que les 3 autres restantes.

Pour déterminer ces 3 parts, il suffit d'analyser le pseudo centre de coupe.

Dès lors, Alice mange une des extrémités de ces parts.
Si Bob, mange une grosse part, Alice continue dans sa lancée.

S'il prend une petite part, Alice continue de manger une grosse.

Suis-je assez clair ?

@Poum45 Je crois que t'es bon pour un exemple parce que j'ai rien pigé

@Insert je suis nul en dessin mais allez :



La position du centre indique les trois grosses parts (G1, G2 et G3).
Alice commence par manger G1 ou G3 (une des extrémités)
Si Bob attaque G2, Alice mange le troisième G sinon elle mange G2.

Quoi qu'il arrive, elle aura plus à manger que Bob.
Du moins, je pense

Edit : bon, si G2 est énorme elle le mange et on en parle plus

@Poum45 Oui ça, c'est quand les coupes sont des pseudo-diamètres, mais c'est pas obligatoire d'après l'énoncé. Elles peuvent être simplement des pseudo-rayons.

Du coup, les cas :


me paraissent beaucoup plus compliqué à résoudre. Surtout quand il y a plus de 6 parts.

Pour moi, c'est plutôt une question d'ordre. Peu importe la forme des parts, le centre tout ça.
Faut imaginer des valeurs disposées en cercle.

Les valeurs représentent la taille des parts. Bon, on pourrait s'amuser à prendre des fractions de l'unité pour que la somme fasse 1, j'ai la flemme. L'important, c'est d'avoir la plus grosse.
Somme, j'entends.
Hum.
Bon, bref.

Tout dépend de l'ordre dans lequel sont disposées les valeurs. Parfois, commencer par la plus grande fait que les autres grandes valeurs ne sont disponibles que pour Bob.
Mais je vois pas trop de stratégie ; à chaque fois, je teste des scénarios.

Insert a raison, il faut raisonner avec des valeurs. Le fait de vouloir partitionner les parts (de sorte à avoir la moitié des parts plus grosse que le reste) est une bonne idée, mais il faut partitionner de manière astucieuse, pour être sûr qu'Alice puisse manger toutes ces parts.

De retour après une nuit de sommeil.

Merci pour les quelques précisions et surtout schémas qui aide à la compréhension du problème.

La petite difficulté est que nous pouvons connaitre la stratégie du choix de portion de Bob.

Le problème peut se transcrire sous une forme d'arbre.
Un nœud = une portion choisie.
Chaque nœud a donc deux nœuds fils correspondant aux deux choix possibles de portion, sauf le nœud racine
qui aura autant de fils qu'il y a de portions (pour le choix initial d'Alice)

La profondeur de l'arbre est liée à la personne qui choisi.
- Profondeur 0 (nœud racine pour le départ)
- Profondeur 1 = choix d'Alice
- Profondeur 2 = choix de Bob
- ...
- Profondeur impaire = choix d'Alice
- Profondeur paire = choix de Bob
- ...

En associant à chaque nœud la surface de la portion correspondante (le nœud racine n'a pas de surface), la résolution du problème consiste à rechercher le meilleurs parcours de l'arbre depuis la racine jusqu'à une feuille.

En terme d'algo, on peut déjà faire un parcours brutal (exhaustif) de l'arbre...
Mais l'intérêt devient limité.

Edit : les nœuds de l'avant dernier niveau ne peuvent avoir qu'un nœud fils (car Bob ne choisi pas sa dernière portion : il est obligé de la prendre la dernière qui reste).

Voici l'arbre pour une portion découpée en 4 portions.
Les portions sont numérotés l'une après l'autre (dans un sens donné mais sans importance).

0 noeud racine
+
1 2 3 4 choix initial d'Alice
+---+ +---+ +---+ +---+
2 4 1 3 2 4 1 3 choix de Bob
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
3 4 2 3 3 4 1 4 1 4 1 2 2 3 1 2 choix d'Alice
+ + + + + + + + + + + + + + + +
4 1 3 2 4 3 4 1 4 1 2 1 3 2 2 1 dernière portion prise par Bob

Arf, zut, il y a pas de police avec une taille fixe??

Dans le cadre de l'exemple d'Alex, on peut donc voir que la suite 13, 13, 11 est la plus grande possible (n/2).
Donc, on attaque par le 13 du bord.

Quand il y a 2n parts de pizza, Alice doit choisir n parts.
Or combien de façon a-t-elle de choisir ?


Et on sait aussi que quand on distribue la pizza entre deux personnes, il y a toujours une des deux personnes qui a la moitié ou plus de la pizza.

Donc on sait qu'il y a
sélections qui permettent d'avoir le plus de pizza.
J'ai tenté des stratégies, mais rien ne fonctionne vraiment

Je vais essayer d'aiguiller sans donner la réponse.

Déjà, oubliez les calculs et les arbres, vous allez vous compliquer la vie.
Ensuite Insert dit une chose capitale. Il y a 2n parts, donc chacun en mange n, et inévitablement, une personne mange au moins la moitié de la pizza.

Du coup, si on trouve n parts qu'on est sûrs de pouvoir prendre, et qui représentent plus de la moitié de la pizza, c'est gagné. Encore faut-il trouver n part que l'on soit sûrs de pouvoir prendre.

Citation :

Pour moi c'est la bonne piste, mais je ne comprends peut-être pas bien ce que tu entends par parts paires vs impaires.

On découpe la pizza en deux en séparant les parts paires et impaires.
On les rassemble (pour reformer) et regarde quelle moitié est la plus grosse ?

Ne me demandez pas de dessins, c'est juste une intuition

@Fastwood
Je voulais dire on appelle une part "1" (genre celle qui contient le vrai centre de la pizza par exemple, ou la plus petite...) et on assigne un numéro aux parts restantes dans le sens... horaire disons.

On a donc des parts numérotées de "1" à "2n" (parce que ce qui va de soi va toujours mieux en le disant : 2n parce qu'il y a un nombre pair de parts, et chacun recevra n. Je dis ça pour ceux qui nous lisent mais ne participent pas forcément ^^)

Bref, je pensais faire deux groupes : les parts avec un numéro pair et celles avec un numéro impair.
Mais...
Après que tout le monde a choisi ses parts, rien ne dit que Bob n'aura que des parts de même parité. C'est pour ça que je voyais pas quoi faire avec ça.

Je me disais aussi : il suffit qu'Alice classe les parts dans l'ordre et se débrouille pour prendre les n plus grosses.
"Oui mais suivant comment elles sont disposées, ça sera peut-être pas possible"
En effet. Cependant, même sans avoir complètement les n plus grosses, on peut s'en sortir.
Il suffit qu'elle ait suffisamment de grosses parts pour se permettre de faire avec 1 ou 2 ou 3... parts plus petites.
Mais j'ai rien réussi à formaliser.

Citation :

Mmm, peut-être qu'Alice peut forcer Bob à n'avoir que des parts d'une certaine parité ?

Citation :

Putain, je suis vraiment trop con...

Tsss...
Bon, en fait, la réponse est évidente ^^

Citation :

Lorsque la lumière est allumée, tout le monde voit l'interrupteur

Citation :

je la ressortirai celle-là

@Insert Pas mal
Il faudrait pas qu'un Koreusien ait l'idée de mettre ça en signature