Sujet 1. Découpages pâtissiers [exposé]
nb d'élèves : 4 & 5 (Guillaume BARZANTI, Mathieu CALES, Arnaud FRAYRET, Georges GOETZ & Noélie CARRARETTO, Alix PASCO, Clément RIBAT, Marc ROCHER, Marion TUVACHE)

La question de base est la suivante : combien de parts de gâteau est-il possible d'obtenir en un nombre donné n de coups de couteau (ou "découpes") ?

Version n°1.

On suppose que le gâteau a la forme d'un disque sans épaisseur (on ne peut pas le couper en deux dans le sens de l'épaisseur) et que la lame du couteau a une longueur supérieure au diamètre du gâteau ; par ailleurs, on ne cherche pas à faire des parts égales ...
[De plus on laisse les morceaux en place tout le temps des découpes, ce qui interdit desuperposer des morceaux]

Combien de parts peut-on alors obtenir avec 4 découpes ? 5 découpes ? n découpes (il faut trouver une formule générale donnant le nombre de parts en fonction du nombre de découpes) ?

Il s'agit là d'un problème classique, mais qui peut nous inspirer...

Autres versions.

En effet, nous pouvons considérer par exemple les questions suivantes :

• Que se passe-t-il si l'on remplace le gâteau par un beignet (voir ci-dessous) ?
• Que se passe-t-il si l'on considère une rangée de p gâteaux (voir ci-dessous), ou de beignets, et un couteau dont la lame permet d'atteindre l'ensemble des gâteaux ?
• Que se passe-t-il si la longueur de la lame est égale au rayon du disque et non plus au diamètre ?
• Que se passe-t-il si l'on prend en compte l'épaisseur du gâteau et si l'on s'autorise les coupes "horizontales" ? (cette fois, on peut par exemple obtenir 8 parts avec 3 découpes...)
  

Dans chaque cas, le problème consiste à trouver une formule générale donnant le nombre de parts en fonction du nombre de découpes...

Comme pour la version n°1, la technique à utiliser est généralement :

- construire graphiquement les premiers nombres,
- essayer de "deviner" la formule,
- démontrer que la formule est correcte !

Il existe de nombreux jeux d'allumettes et celui qui nous intéresse est le suivant :

Deux joueurs disposent d'un tas de 50 allumettes et retirent à tour de rôle un certain nombre d'allumettes.

- Le premier joueur peut retirer 1 ou 2 allumettes du tas.
- Lorsqu'un joueur a retiré n allumettes, le joueur suivant peut en retirer au maximum 2n.
- Le joueur qui retire la dernière allumette est déclaré perdant.

Le problème qui nous intéresse est le suivant :

• existe-t-il une stratégie gagnante pour le premier joueur ? Pour le deuxième joueur ? Et si oui laquelle !

La technique à mettre en oeuvre est une technique classique en théorie des jeux, qui consiste à déterminer les "positions gagnantes"... Une "position" est une information qui permet de décrire la situation du jeu au moment où l'un des joueurs doit jouer. Dans notre exemple, une position peut être représentée par un couple (a,b), où a représente le nombre d'allumettes restant dans le tas et b le nombre d'allumettes retirées par le joueur précédent (on sait ainsi que l'on pourra retirer entre 1 et 2b allumettes).

Il est facile de se convaincre par exemple que (1,b) est toujours une position perdante (il reste une allumette, on a donc perdu) alors que (2,b) est toujours une position gagnante (en enlevant une allumette, on conduit l'adversaire à une position perdante...).

Ainsi, une position perdante est une position qui ne permet jamais de gagner (on suppose que l'adversaire ne commet jamais de faute) et une position gagnante est une position qui envoie l'adversaire dans une position perdante... simple, non ?

Notre probléme consiste alors à répondre à la question suivante :

• Quelles sont les positions gagnantes ? et, en particulier, (50,1) est-elle une position gagnante ?
  
  Remarquons que (50,1) modélise bien la position initiale car le premier joueur peut retirer 1 ou 2 allumettes...
  
  La méthode à suivre peut être la suivante :
  Considérer dans un premier temps un nombre plus faible d'allumettes (avec 1 ou 2 cela doit être trivial !).
  Essayer de deviner comment se déterminent les positions gagnantes (et perdantes !).
  
• On pourra également considérer différentes variantes de ce jeu, selon l'inspiration :
  
  on peut par exemple supposer qu'il y a au départ 2 tas de 25 allumettes et qu'à chaque étape les allumettes retirées par un joueur doivent appartenir à un même tas ...