Sujets Math.en.Jeans 2010-2011

Un carré magique est un carré subdivisé en n² petits carrés
identiques, dont chacun contient un nombre de 1 à n²  tel que
les propriétés suivantes soient vérifiées:

1. chaque nombre entre 1 et n² apparaît dans un seul petit
     carré,
2. la somme des nombres dans chaque ligne a la même valeur,
3. la somme des nombres dans les deux diagonales a cette même valeur.

La Nitendo DS a un jeu appelé "Big Brain Academy".

Dans ce jeu, différents types de problèmes doivent être résolus le plus
rapidement possible.

Voici un des problèmes:

Il y a plusieurs lignes verticales. Au sommet de chaque ligne est assis un
animal. Tous les animaux sont différents.

Pour chaque animal en haut des lignes, il y a un animal partenaire en bas,
mais pas nécessairement sur la même ligne.

Parfois, deux lignes verticales consécutives sont connectées par des lignes
horizontales de telle manière que les lignes horizontales ne se touchent pas.

Les animaux commencent à courir le long des lignes verticales, et dès qu'ils
parviennent à un croisement avec une ligne horizontale, ils courent le long
de l'horizontale jusqu'à la ligne connectée verticale; puis continuent de la
parcourir vers le bas.

Dès que le jeu démarre, le joueur doit construire rapidement des lignes
horizontales supplémentaires, de manière à ce que chaque animal puisse
rencontrer son partenaire en bas des lignes verticales.

Considérons un réseau de lignes verticales et horizontales, telles que
décrites ci-dessus:

•   Les animaux peuvent-ils retrouver leur partenaire quelque soit la
  façon dont sont tracées les lignes horizontales ?
  
  
• Est-ce possible de construire un réseau, pour lequel deux animaux se
    retrouvent sur la même ligne ?
  
  
• Est-il possible de tracer des lignes horizontales de manière à ce que
    chaque animal se retrouve sur une ligne verticale arbitraire ?