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

Partagez
 

 3° Exo Olympiade Vietnam 2007

Aller en bas 
AuteurMessage
kaderov
Maître
kaderov

Masculin Nombre de messages : 89
Age : 51
Localisation : Casablanca
Date d'inscription : 03/07/2007

3° Exo Olympiade Vietnam 2007 Empty
MessageSujet: 3° Exo Olympiade Vietnam 2007   3° Exo Olympiade Vietnam 2007 EmptyMer 25 Juil 2007, 11:46

Dans une compétition mathématique,quelques conccurents sont des amis (L'amitié est toujours mutuelle).
Nous appelons une "clique" un groupe de conccurents qui chacun à au moins un amis dans ce groupe ( en particulier un groupe contenant deux amis est une "clique")
Le nombre des membres d'une "clique" est appelé une "taille"
nous supposons que dans une compétition que la plus grande "taille" est paire.Montrer que les conccurents peuvent être distribués dans deux salles telles que la plus grande taille d'une "clique" dans la première salle est la même que la plus grande "taille" d'une "clique" dans la deuxième salle.
au cas ou ma traduction n'est pas bonne voici la version originale en anglais Razz


In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitiors is a clique.) The number of members of a clique is called its size.

Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.


Dernière édition par le Mer 25 Juil 2007, 12:40, édité 2 fois
Revenir en haut Aller en bas
kaderov
Maître
kaderov

Masculin Nombre de messages : 89
Age : 51
Localisation : Casablanca
Date d'inscription : 03/07/2007

3° Exo Olympiade Vietnam 2007 Empty
MessageSujet: Re: 3° Exo Olympiade Vietnam 2007   3° Exo Olympiade Vietnam 2007 EmptyMer 25 Juil 2007, 11:50

D'après les rumeurs, cet EXO est très très difficile et apparement seul un Chinois l'a résolu pendant le compétition!!!!!!!!

je souhaite une bonne chance à notre équipe Marocaine cheers
Revenir en haut Aller en bas
facebabe
Débutant


Nombre de messages : 1
Date d'inscription : 17/08/2007

3° Exo Olympiade Vietnam 2007 Empty
MessageSujet: Re: 3° Exo Olympiade Vietnam 2007   3° Exo Olympiade Vietnam 2007 EmptyVen 17 Aoû 2007, 16:27

Voila la solution que je vois, peu vérifiée ... En tout cas, je suis certain qu'elle est utile, même si il y a une erreur.

Préliminaire:

Clique majeure: taille 2m.

On considère les deux pièces A et B.

Etat initial: les 2m éléments de la clique majeure dans la pièce B et le reste des éléments dans la pièce A.

Processus:

Etape 1: on déplace des éléments de la pièce B à la pièce A un à un. Par conséquent, la plus grande clique de la pièce B diminue de 1 à chaque étape et la plus grande clique de la pièce A augmente de 0 ou 1 à chaque étape.

On note A(k) (resp B(k)) la taille de la plus grande clique de la pièce A (resp. la pièce B) à la k-ième étape (après k déplacements de la pièce B vers la pièce A)

On remarquera, en particulier, que B(0) = 2m, B(k) = 2m -k.

L'étape 1 s'arrête dans l'un des deux cas suivants

i) Soit quand A(k) = B(k) (on a alors gagné)

ii) Soit quand A(k) + 1 = B(k)

Il est facile de s'assurer que l'on se trouvera forcément dans l'une des deux configurations à un moment donné (A(k) est croissant et B(k) est décroissant, et ils varient de 1 au maximum...)



Etape 2: On se trouve donc dans la configuration pour laquelle A(k) + 1 = B(k).

Là, ca se complique. Si l'on déplace un élément de plus de B vers A, deux cas possibles:

i) A(k+1) = A(k) et dans ce cas on a gagné car B(k+1) = B(k) - 1 = A(k) = A(k+1).

ii) le cas chiant: A(k+1) = A(k) + 1. la taille de la(les) clique(s) de plus grande taille de la pièce A a augmenté de 1 et on a A(k+1) ) = B(k) = 1 + b(k+1).
Il va falloir faire un nouveau déplacement, cette fois de A vers B!!!!

La remarque qui débloque tout:

Si l'une des cliques (il peut y en avoir plusieurs) de taille A(k+1) à l'étape k+1 ne contient pas l'intégralité des k+1 éléments de la clique majeure initiale passés de B à A, alors on a gagné car il suffit de renvoyer cet élément de A à B et la clique en question restera de taille A(k+1) (car le passagé de cet élément de A à B ne change rien vu qu'elle ne le contenait pas!) et la clique de la pièce B sera de nouveau de taille A(k+1).

Par conséquent, on peut supposer que toutes les cliques de taille A(k+1) dans la pièce A à l'étape k+1 contiennent les k+1 éléments de la clique majeure initiale passés de B à A. On y est presque!!

Soit q le nombre de cliques de la pièce A, de taille A(k+1) à l'étape k+1. On choisit un élément dans chacune de ces cliques (il peut y en avoir qui appartiennent à plusieurs des q cliques, peu importe) et on les fait passer dans la pièce B. Par conséquent, la clique de plus grande taille dans la pièce A devient A(k+2) = A(k+1) -1 (clair!).

Qu'en est t-il de B(k+2)? on espère qu'il reste égal à B(k+1) = A(k+1) - 1 = A(k+2)... Eh bien, c'est le cas. en effet, qu'a-t-on dans la pièce B à l'étape k+2?

- les 2m - (k+1) éléments de la clique majeure initiale +
- q (ou moins) éléments venus de chacune des cliques de la pièce A dont on a parlé plus haut. On remarquera que tous ces éléments sont amis avec les k+1 éléments provenant de B ...

supposons que l'on arrive à former une clique de taille strictement plus grande que B(k+1) = 2m - (k+1). Dans ce cas, si on associe cette clique avec les k+1 éléments initiaux de la clique majeure qui sont dans la pièce A, on obtient une clique de taille strictement supérieure à 2m (voir la remarque en gras au dessus) . D'où la contradiction.
Revenir en haut Aller en bas
Contenu sponsorisé




3° Exo Olympiade Vietnam 2007 Empty
MessageSujet: Re: 3° Exo Olympiade Vietnam 2007   3° Exo Olympiade Vietnam 2007 Empty

Revenir en haut Aller en bas
 
3° Exo Olympiade Vietnam 2007
Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» dernières photos
» Ephéméride 27 Août......
» Ephéméride 22 Juillet......
» Ephéméride 22 Septembre.....
» 01/01/2000 = 11/09/2007

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