Aide pour les futurs mathématiciens
 
AccueilAccueil  PortailPortail  RechercherRechercher  S'enregistrerS'enregistrer  Connexion  

Partagez
 

 Marathon de combinatoire

Aller en bas 
AuteurMessage
Dijkschneier
Expert sup


Masculin Nombre de messages : 1482
Age : 25
Date d'inscription : 12/12/2009

Marathon de combinatoire Empty
MessageSujet: Marathon de combinatoire   Marathon de combinatoire EmptyVen 27 Mai 2011, 14:36

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.
Revenir en haut Aller en bas
http://dijkschneier.freehostia.com
darkpseudo
Expert sup


Masculin Nombre de messages : 817
Age : 26
Date d'inscription : 31/10/2009

Marathon de combinatoire Empty
MessageSujet: Re: Marathon de combinatoire   Marathon de combinatoire EmptyVen 27 Mai 2011, 19:34

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 ?.
Revenir en haut Aller en bas
Dijkschneier
Expert sup


Masculin Nombre de messages : 1482
Age : 25
Date d'inscription : 12/12/2009

Marathon de combinatoire Empty
MessageSujet: Re: Marathon de combinatoire   Marathon de combinatoire EmptyVen 27 Mai 2011, 20:18

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:
 
Revenir en haut Aller en bas
http://dijkschneier.freehostia.com
Bensouda
Féru


Masculin Nombre de messages : 67
Age : 25
Date d'inscription : 28/02/2011

Marathon de combinatoire Empty
MessageSujet: Re: Marathon de combinatoire   Marathon de combinatoire EmptyLun 30 Mai 2011, 13:34

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 .
Revenir en haut Aller en bas
n.naoufal
Expert sup
n.naoufal

Masculin Nombre de messages : 595
Age : 28
Localisation : France.
Date d'inscription : 05/11/2008

Marathon de combinatoire Empty
MessageSujet: Re: Marathon de combinatoire   Marathon de combinatoire EmptyLun 30 Mai 2011, 19:03

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 Smile.
Revenir en haut Aller en bas
Bensouda
Féru


Masculin Nombre de messages : 67
Age : 25
Date d'inscription : 28/02/2011

Marathon de combinatoire Empty
MessageSujet: Re: Marathon de combinatoire   Marathon de combinatoire EmptyLun 30 Mai 2011, 19:05

Hahaha ! Very Happy
Revenir en haut Aller en bas
Dijkschneier
Expert sup


Masculin Nombre de messages : 1482
Age : 25
Date d'inscription : 12/12/2009

Marathon de combinatoire Empty
MessageSujet: Re: Marathon de combinatoire   Marathon de combinatoire EmptyDim 05 Juin 2011, 20:12

Solution au problème 3 :
Spoiler:
 
Revenir en haut Aller en bas
http://dijkschneier.freehostia.com
Dijkschneier
Expert sup


Masculin Nombre de messages : 1482
Age : 25
Date d'inscription : 12/12/2009

Marathon de combinatoire Empty
MessageSujet: Re: Marathon de combinatoire   Marathon de combinatoire EmptyDim 05 Juin 2011, 20:29

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.
Revenir en haut Aller en bas
http://dijkschneier.freehostia.com
Dijkschneier
Expert sup


Masculin Nombre de messages : 1482
Age : 25
Date d'inscription : 12/12/2009

Marathon de combinatoire Empty
MessageSujet: Re: Marathon de combinatoire   Marathon de combinatoire EmptyJeu 09 Juin 2011, 20:59

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).



Dernière édition par Dijkschneier le Jeu 09 Juin 2011, 21:03, édité 1 fois
Revenir en haut Aller en bas
http://dijkschneier.freehostia.com
Dijkschneier
Expert sup


Masculin Nombre de messages : 1482
Age : 25
Date d'inscription : 12/12/2009

Marathon de combinatoire Empty
MessageSujet: Re: Marathon de combinatoire   Marathon de combinatoire EmptyJeu 09 Juin 2011, 21:02

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).
Revenir en haut Aller en bas
http://dijkschneier.freehostia.com
Dijkschneier
Expert sup


Masculin Nombre de messages : 1482
Age : 25
Date d'inscription : 12/12/2009

Marathon de combinatoire Empty
MessageSujet: Re: Marathon de combinatoire   Marathon de combinatoire EmptyJeu 30 Juin 2011, 11:48

Allons, dépassons la barre symbolique de '"deux" pages afin qu'on ne dise pas après que ce marathon était complètement raté Laughing.
Revenir en haut Aller en bas
http://dijkschneier.freehostia.com
symizter
Débutant


Masculin Nombre de messages : 5
Age : 26
Date d'inscription : 14/04/2011

Marathon de combinatoire Empty
MessageSujet: Re: Marathon de combinatoire   Marathon de combinatoire EmptySam 02 Juil 2011, 13:24

- Incorrect.


Dernière édition par symizter le Sam 02 Juil 2011, 13:35, édité 1 fois
Revenir en haut Aller en bas
yassine sbai
Féru


Masculin Nombre de messages : 32
Age : 25
Date d'inscription : 26/02/2011

Marathon de combinatoire Empty
MessageSujet: Re: Marathon de combinatoire   Marathon de combinatoire EmptySam 02 Juil 2011, 13:29

symizter, chaque ligne et chaque colonne doit contenir au plus 2 couleurs
Revenir en haut Aller en bas
Contenu sponsorisé




Marathon de combinatoire Empty
MessageSujet: Re: Marathon de combinatoire   Marathon de combinatoire Empty

Revenir en haut Aller en bas
 
Marathon de combinatoire
Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum des amateurs de maths :: Olympiades :: Combinatoire-
Sauter vers: