Marathon de combinatoire

Je lance un nouveau marathon de combinatoire axé sur la préparation aux problèmes combinatoires de l'IMO, et j'espère que la participation sera active.
Les règles du marathon ne sortent pas du lot :
- Numéroter clairement les problèmes, et citer le numéro du problème dans la solution que l'on en donne.
- Donner préférablement une estimation de la difficulté du problème.
- Spoiler les solutions afin de ne pas biaiser l'esprit des participants.
- Veiller à ne pas répéter les problèmes.
- Ne pas indiquer les sources des problèmes (nom de la compétition etc.).
- Ne pas poster de solutions incomplètes et par conséquent, ne pas attendre de confirmation pour proposer à nouveau un problème.

Problème 1 : (* : une étoile)
Montrer que si IN* est partitionné en deux ensembles A et B non vides tels que :
x,y de A et x différent de y ===> x+y de A
x,y de B et x différent de y ===> x+y de A
x de A et y de B ===> x+y de B,
alors A contient exactement les éléments pairs et B les éléments impairs.

Solution du Problème 1 :

Spoiler:

Problème 2(**) : [b]
On place 2010 arbres sur chaque arbre un corbeau vient ce placer , à chaque étape deux corbeaux ce déplacent vers un arbre voisin , est-il possible que tout les corbeau ce retrouvent sur le même arbre après un certain nombre d'étapes ?.

darkpseudo a écrit:

je pense que tu as oublié de mentionner que tes ensembles sont disjoints

C'est inutile étant donné la définition d'une partition.

Solution au problème 2 :

Spoiler:

Problème 3 :
Dans un pays, 11 villes sont reliées deux à deux soit par une autoroute soit par une ligne de chemin de fer ( qui fonctionnent dans les 2 sens ) .Prouver qu'il existe forcément un pont sur lequel soit une autoroute passe au dessus d'une autre, soit une voie de chemin de fer passe au dessus d'une autre .

Facilement faisable par la Théorie des graphes, je pense que c'est le même que celui donné dans les tutoriaux Animath sur les aéroports. ça me rappelle les années du lycée .

Hahaha !

Problème 4 : (** : deux étoiles)
Soient a_1, a_2, a_3, ..., a_(n²+1) des réels distincts.
Montrer qu'il existe une fonction sigma strictement croissante telle que la suite a_(sigma(i)) pour i=1 jusqu'à i=(n+1) soit strictement monotone.
En d'autres termes : montrer que pour toute suite de (n²+1) éléments distincts, il existe une sous-suite de n+1 éléments strictement monotone.

Solution au problème 4 :
On associe à chaque terme ai la quantité ti qui représente la longueur maximale d'une sous-suite croissante qui commence à ai.
S'il existe un ti qui soit >=n+1, on a fini. Sinon, tous les ti sont 1<=ti<=n, et peuvent donc prendre n valeurs différentes. D'après le principe des tiroirs, on a : E((n²+1)/n)+1=n+1 ti qui ont la même valeur.
Montrons alors que les ai associés à ces (n+1) ti forment une sous-suite décroissante, ce qui permettrait de conclure.
Soient a(u) et a(v) avec u<v ayant la même quantité t (i.e : t(u)=t(v)). Si a(u)<a(v), alors en ajoutant a(u) à la suite croissante de longueur maximale t(v) commençant à a(v), on obtient une suite croissante de longueur t(v)+1, ce qui vient en contradiction avec le fait que t(u)=t(v). D'où : a(u)>a(v).

Problème 5 : (** : deux étoiles)
Montrer qu'on ne peut colorier un tableau 10x10 avec 10 couleurs tel que chaque couleur remplisse 10 cases et que chaque ligne et colonne soit au plus bichromatique (i.e, soit colorié avec au plus 2 couleurs).

Allons, dépassons la barre symbolique de '"deux" pages afin qu'on ne dise pas après que ce marathon était complètement raté .

symizter, chaque ligne et chaque colonne doit contenir au plus 2 couleurs