Concours > Concours #4

Description

Afin d'occuper ces vacances de Printemps (désolé la zone C pour les Français), voici un concours (que dis-je, un marathon !) constitué uniquement de problèmes combinatoires. Dix problèmes de niveaux variés s'enchaineront pendant un peu plus d'une semaine, chacun étant disponible pendant 42 heures.

Les problèmes dont le numéro est congru à $1$ modulo $3$ seront les plus abordables (niveau 1/2 sur Mathraining), ceux congrus à $2$ modulo $3$ de difficulté intermédiaire et ceux congrus à $0$ modulo $3$ les plus avancés. La seule exception sera le problème $10$, le plus compliqué, de difficulté comparable à un niveau 5 sur le site.

Organisateur du concours : 13Corentin Bodart.

Problème #1

Solutions acceptées du vendredi 12 avril 2019 à 6h00 au samedi 13 avril 2019 à 23h59 (heures belges).
Énoncé
Un tournoi de badminton réunit $n$ compétiteurs. Durant le tournoi, chaque paire de joueurs se rencontre une et une seule fois. À la fin de la compétition, on veut arranger les joueurs en une ligne pour une photo, de sorte qu'un joueur ait toujours battu le joueur directement à sa gauche. Prouvez qu'un tel arrangement est toujours possible.

Remarque : Il n'y a pas de match nul au badminton.
Statistiques
Tenté par 38 personnes
Scores parfaits : 35

Problème #2

Solutions acceptées du samedi 13 avril 2019 à 6h00 au dimanche 14 avril 2019 à 23h59 (heures belges).
Énoncé
Votre ami Vladimir veut vous aider à résoudre le problème #1. Étant un riche oligarque russe, il décide de fixer les résultats des différentes parties avec les participants de sorte à vous faciliter la vie. Montrer qu'il peut le faire de sorte qu'au moins $\frac{n!}{2^{n-1}}$ arrangements des joueurs sur la photo satisfassent la condition du problème #1.
Statistiques
Tenté par 16 personnes
Scores parfaits : 10
Origine du problème : Théorème de Szele

Problème #3

Solutions acceptées du dimanche 14 avril 2019 à 6h00 au lundi 15 avril 2019 à 23h59 (heures belges).
Énoncé
Trouver tous les triplets $(s,a,f)\in\mathbb N^3$ pouvant être les nombres de sommets, d'arêtes et de faces d'un polyèdre convexe (non-dégénéré) dont toutes les faces sont triangulaires.

Bonus : Y a-t-il d'autres possibilités si l'on retire la condition "convexe" ?
Statistiques
Tenté par 17 personnes
Scores parfaits : 11
Origine du problème : Équations de Dehn-Sommerville en dimension 3

Problème #4

Solutions acceptées du lundi 15 avril 2019 à 6h00 au mardi 16 avril 2019 à 23h59 (heures belges).
Énoncé
Ivan possède un paquet de $52$ cartes usuel, qu'il a préalablement mélangé. Il pioche et révèle les cartes une par une, sans les remettre dans le paquet. Juste avant de retourner chaque carte, il parie sur la couleur de celle-ci. Afin de maximiser son nombre de succès, il parie à chaque fois sur la couleur la plus représentée parmi les cartes restantes (si plusieurs couleurs satisfont cette description, il choisit au hasard parmi celles-ci). Prouver qu'il pariera au moins $13$ fois sur la bonne couleur.

Remarque : La couleur d’une carte est la suite à laquelle il appartient, c’est-à-dire cœur, carreau, trèfle ou pique.
Statistiques
Tenté par 25 personnes
Scores parfaits : 22

Problème #5

Solutions acceptées du mardi 16 avril 2019 à 6h00 au mercredi 17 avril 2019 à 23h59 (heures belges).
Énoncé
$100$ filles et $100$ garçons se font face sur deux lignes parallèles (les filles sur une ligne et les garçons sur l’autre). Chaque garçon choisit une fille (il est possible que plusieurs garçons choisissent une même fille), marche vers celle-ci en suivant le plus court chemin et puis reviennent à leur place. On suppose que leurs chemins ne se croisent pas. Ensuite, les filles font la même chose : chacune choisit un garçon, marche vers lui en s'assurant que leurs chemins ne se croisent pas. Prouver qu'il existe une fille et un garçon s'étant choisis l'un l'autre.
Statistiques
Tenté par 21 personnes
Scores parfaits : 16
Origine du problème : KöMaL, Novembre 2001, Problème B.3500

Problème #6

Solutions acceptées du mercredi 17 avril 2019 à 6h00 au jeudi 18 avril 2019 à 23h59 (heures belges).
Énoncé
Soient $n$ sous-ensembles distincts $A_1,A_2,\ldots,A_n$ de $\{1,2,\ldots,n\}$. Montrer qu’il existe un $x\in\{1,2,\ldots,n\}$ tel que
\[ A_1\setminus\{x\},\,A_2\setminus\{x\},\ldots,\,A_n\setminus\{x\} \] soient également distincts.
Statistiques
Tenté par 20 personnes
Scores parfaits : 17
Origine du problème : Théorème de Bondy

Problème #7

Solutions acceptées du jeudi 18 avril 2019 à 6h00 au vendredi 19 avril 2019 à 23h59 (heures belges).
Énoncé
Considérons un ensemble $S$ de $n\ge 3$ points du plan. Supposons que trois points quelconques de $S$ délimite toujours un triangle d'aire inférieure à $1$. Montrer que $S$ est contenu dans un triangle d'aire $4$.
Statistiques
Tenté par 16 personnes
Scores parfaits : 13

Problème #8

Solutions acceptées du vendredi 19 avril 2019 à 6h00 au samedi 20 avril 2019 à 23h59 (heures belges).
Énoncé
Un sous-ensemble non-vide $S\subseteq\{1,2,\ldots,n\}$ est appelé décent si la moyenne arithmétique de ses éléments est entière. Montrer que le nombre de sous-ensembles décents à la même parité que $n$.
Statistiques
Tenté par 13 personnes
Scores parfaits : 12
Origine du problème : Putnam 2002, Problème A3

Problème #9

Solutions acceptées du samedi 20 avril 2019 à 6h00 au dimanche 21 avril 2019 à 23h59 (heures belges).
Énoncé
Sur une grille $(4n+2)\times(4n+2)$, une tortue peut se déplacer entre cases ayant un côté en commun. La tortue part d'une case dans un coin de la grille et visite chaque case une et une seule fois avant de se retrouver dans sa case de départ. Quel est (en fonction de $n$) le plus grand entier $k>0$ tel qu'il existe une ligne ou une colonne de la grille dans laquelle la tortue est entrée au moins $k$ fois (quelque soit le chemin emprunté) ?
Statistiques
Tenté par 9 personnes
Scores parfaits : 8
Origine du problème : Canadian Mathematical Olympiad 2015, Problème 3

Problème #10

Solutions acceptées du dimanche 21 avril 2019 à 6h00 au lundi 22 avril 2019 à 23h59 (heures belges).
Énoncé
Un magicien et son assistant performent un tour de magie :

Tout d'abord, le magicien se fait enfermer par son assistant, de sorte qu'il ne puisse rien voir ou entendre. Ensuite, l'assistant invite un membre de l'audience et lui demande de placer une pièce sur chaque case d'un échiquier $n\times n$, soit sur pile, soit sur face. De plus, il lui demande d'indiquer une case $C$ de l'échiquier. L'assistant choisit alors une case (pas nécessairement la même) et retourne la pièce située dessus. Finalement, l'assistant libère le magicien qui, à la seule vue de l'échiquier, devine la case $C$.

Pour quelles valeurs de $n$ ce tour est-il possible ?
Statistiques
Tenté par 9 personnes
Scores parfaits : 6
Origine du problème : Italian Mathematical Olympiad 2013, Problème 6 // Tournament of Town, Fall 2007, Senior A-Level, Problème 5