CultureMath
Les algorithmes gloutons offrent une solution pratique, mais pas toujours optimale, à de nombreux problèmes arithmétiques...
Question du jeudi #63 :
-
On pose un monomino sur une des cases d'un échiquier $8\times 8$. Peut-on paver les $63$ cases restantes par 21 triominos « coudés » ?
-
Même question avec $21$ triominos « droits ».
Question du jeudi #61 : On répartit les entiers de $1$ à $n$ en $k$ classes de telle sorte que deux éléments d'une même classe ne se divisent jamais l'un l'autre. Quel est la plus petite valeur possible pour $k$ ?
Question du jeudi #53 : Lors du Tournoi des Six Nations, on dit qu'une équipe réalise un Grand Chelem si elle bat toutes les autres équipes. Pour cette question, on dira qu'une équipe A réalise un Petit Chelem si, à chaque fois que l'on considère une autre équipe B, alors A a battu B ou A a battu une équipe qui a battu B.
Par exemple, lors de l'édition 2015 du Tournoi, les Gallois n'ont pas réalisé de Grand Chelem, puisqu'ils ont perdu contre les Anglais, mais ils ont réalisé un Petit Chelem, puisqu'ils ont battu toutes les autres équipes, et en particulier les Irlandais, qui ont à leur tour battu les Anglais. (L'Irlande et l'Angleterre ont elles aussi réalisé un Petit Chelem).
Montrer que quand il n'y a pas de match nul, une équipe au moins réalise toujours un Petit Chelem.
On rappelle que lors du Tournoi des Six Nations, chaque équipe affronte toutes les autres exactement une fois.
Question du jeudi #52 : Soit $\Omega$ un ensemble à $n$ éléments. Combien y a-t-il de couples $(A,B)$ de parties de $\Omega$ telles que $A \cup B = \Omega$ ?
Question du jeudi #48 : Lors d'un tournoi de Quidditch, quatre équipes s'affrontent une fois chacune. Il est alors possible de lister les équipes, de telle sorte que chacune ait battu la suivante : par exemple, Gryffondor a battu Poufsouffle, qui a battu Serdaigle, qui a battu Serpentard.
Est-il toujours possible de faire une telle liste ? Quid si le tournoi voit s'affronter plus de quatre équipes ? On supposera dans cette question qu'un match de Quidditch ne peut pas être nul.
Question du jeudi #47 : 2015 jetons bicolores (blancs d'un côté, noirs de l'autre) sont posés sur une table. Alice et Bob jouent alors à un (long) jeu : chacun leur tour, ils ont le choix entre retourner ou retirer un certain nombre de jetons de la même couleur. Il est interdit de ne rien faire. Le vainqueur est celui qui retire le dernier jeton.
Qui peut s'assurer de gagner ?
Question du jeudi #40 : Alice et Bob ont été capturés par Ève. Celle-ci leur propose de jouer pour leur libération. Ève va placer sur un échiquier 64 pièces de monnaie. Il y aura ainsi une pièce sur chaque case, soit sur « pile », soit sur « face ». Elle fera ensuite venir Alice, lui montrera l'échiquier, et lui désignera une des cases. Alice devra retourner une des pièces. Ève fera alors sortir Alice et entrer Bob, qui devra, en regardant l'échiquier, trouver quelle case a été désignée par Ève.
Avant le jeu, Alice et Bob ont tout le temps de mettre au point une stratégie commune, mais une fois que le jeu commence, ils ne pourront plus communiquer : la seule information transmise par Alice à Bob le sera par l'intermédiaire de l'échiquier. Pouvez-vous trouver une stratégie qui permette à Alice et Bob d'être sûrs de gagner ?
Question du jeudi #39 : On place n points sur un cercle et l'on trace toutes les cordes reliant ces deux points. On suppose en outre que les cordes sont en position générale, c'est-à-dire que trois cordes ne sont jamais concourantes. Combien de points d'intersection y aura-t-il à l'intérieur du disque ?
Question du jeudi #30 : On considère un paquet de jetons de trois couleurs (rouge, vert et bleu). On s'autorise à chaque coup à remplacer deux jetons de couleurs différentes par deux jetons de la troisième couleur.
En partant d'une situation avec $1515$ jetons rouges, $1789$ jetons verts et $2015$ jetons bleus, est-il possible de parvenir à une situation où tous les jetons sont de la même couleur ?
