[Cours premier] Invitation aux debutants.


  • Math&Maroc

    Bien vu,

    Exercice 3
    Demontrez que, parmi les stagiaires d'un stage Animath, il en existe deux qui connaissent exactement le meme nombre d'autres stagiaires. (pas forcement les memes stagiaires, mais seulement le meme nombre). [On suppose que la relation "se connaitre" est reciproque: si a connait b, alors b connait a.]



  • On considere qu'il y a nn stagieres . Si quelqu'un connait 00 personnes donc il n'existe pas qlq'un qui connait n1n -1 personnes . D'autre part , si qlq connait n1n-1 personnes , donc il n'existe pas qlq qui ne connait personne . D'ou le nombre des connaissances possibles est : n1n-1 . Par le principe des tiroirs , (stagieres = chaussetes , le nombre des connaissances = tiroirs ), il existe au moins deux personnes qui connaient le meme nombre d'autres stagieres.



  • @Reda-Mouqed said in [Cours premier] Invitation aux debutants.:

    On considere qu'il y a nn stagieres . Si quelqu'un connait 00 personnes donc il n'existe pas qlq'un qui connait nn personnes ...

    dans tous les cas il est impossible de connaitre nn personnes sauf si tu inclus toi la personne elle-meme. il faut aussi disucter le cas speciales : n=0,1,..n=0,1,..

    Je veux proposer une solution:
    Soit G=(V,E)G=(V,E) le graphe GG, VV l'ensemble des sommets, EE l'enseble des arretes.
    On suppose que V=n|V| = n et E=e|E|=e.

    Pour n=2,3n=2,3 la propriete est correcte.

    Supposant que ca marche pour tous graphe ou Vn|V| \leq n.

    Soit G=(V,E)G'=(V',E') ou V=n+1|V'| = n+1.

    • Si vV\exists v \in V' tel que deg(v)=0 \deg(v) = 0 alors la propriete est correcte pour cet graphe par l'hypothese de recurrence.
    • Sinon, on a n+1n+1 personnes (sommets) et nn valeurs possibles pour deg(vV)deg(v \in V'), donc deux sommets ont le meme degree.

    donc la propriete est correcte pour n+1n+1 aussi.

    ** How to make a solution longer in 3 steps, use induction **



  • Oui vous avez raison , je voulais dire que si une personne connait n1n-1 , donc il n'existe pas qlq'un qui ne connait personne , et la reciproque est aussi vraie (puisque le nombre maximale que qlq'un peut connaitre est n1n-1, et le minimale est : 00 ) . D'ou le nombre de connaissance possible est : (n1)1+1=n1(n-1) -1 +1= n-1
    J'ai pas pu comprendre votre demontration avec les graphes , je suis encore un debutant (noob hhh ) :)



  • @Driouiche-Youness said in [Cours premier] Invitation aux debutants.:

    @Reda-Mouqed said in [Cours premier] Invitation aux debutants.:

    On considere qu'il y a nn stagieres . Si quelqu'un connait 00 personnes donc il n'existe pas qlq'un qui connait nn personnes ...

    dans tous les cas il est impossible de connaitre nn personnes sauf si tu inclus toi la personne elle-meme. il faut aussi disucter le cas speciales : n=0,1,..n=0,1,..

    Je veux proposer une solution:
    Soit G=(V,E)G=(V,E) le graphe GG, VV l'ensemble des sommets, EE l'enseble des arretes.
    On suppose que V=n|V| = n et E=e|E|=e.

    Pour n=1,2,3n=1,2,3 la propriete est correcte.

    Supposant que ca marche pour tous graphe ou Vn|V| \leq n.

    Soit G=(V,E)G'=(V',E') ou V=n+1|V'| = n+1.

    • Si vV\exists v \in V' tel que deg(v)=0 \deg(v) = 0 alors la propriete est correcte pour cet graphe par l'hypothese de recurrence.
    • Sinon, on a n+1n+1 personnes (sommets) et nn valeurs possibles pour deg(vV)deg(v \in V'), donc deux sommets ont le meme degree.

    donc la propriete est correcte pour n+1n+1 aussi.

    ** How to make a solution longer in 3 steps, use induction **

    Une autre solution avec les graphes
    Soit G=(V,E)G=(V,E) le graphe G simple , V l ensemble des sommets , et EE l ensemble des aretes.
    On modélise chaque stagiiaire par un point S1,S2,...SnS_1,S_2,...S_n et la conaissance par une arete.
    On a 0din10\leq d_i \leq n-1
    Si il existe un sommet SiS_i tel que did_i =0 alors il ne peut pas y avoir un sommet SjS_j tel que dj=n1d_j=n-1 donc On a n1n-1 possibités et nn tiroirs donc on a deux sommets avec le meme degré.
    Si il n existe pas de sommet SiS_i tel que di=0d_i=0 on peut directement appliquer le principe des tiroirs pour conclure qu il existe deux sommets avec le meme degré.


  • Math&Maroc

    Avant de passer a l'exercice 4 du cours d'animath, j'aimerais vous proposer un ou deux exercice pour assurer une bonne maitrise de ce principe des tiroirs. Ces exercices sont issues d'une serie de Problem par Yufei-Zhao que vous pouvez consulter depuis son site-web: http://yufeizhao.com/olympiad.html

    Exercice:
    Soit a1,a2,...,ana_1,a_2,...,a_n des entiers naturels positifs. Montrer qu'il est possible de choisir quelques nombres parmi ces entiers, de sorte que leur somme soit divisible par nn.



  • Un petit hint . Pensez à considerer les sommes Sk=a1+a2.......+akS_k=a_1+a_2.......+a_k Et regardez un peu du cote de la division euclidienne



  • Considérons la suite Sk=a1+a2+........+akS_k= a_1+a_2+........+a_k
    Interessons aux termes S1,S2..........SnS_1,S_2..........S_n
    Si l un des termes est divisible par n n c est terminé.
    Sinon considérons le reste de la division euclidiennes des SkS_k par nn . Il y a n1n-1 possibilités donc il existe deux termes Si,SjS_i,S_j avec ii >jj tel que SiS_i et SjS_j ont la meme congruence modulo nn . Donc nn divise SiSj=aj+1+.......+aiS_i-S_j=a_{j+1} +.......+ a_{i}
    Ce qui nous permet de conclure



  • @Tähä-Britäl J'aimerais savoir pourqoui tu as ajouté le 1 ? Au lieu d'écrire [2×10^6/6×10^5] ?



  • @Achraf-Maghous car le nombre de cheveux entre 0 et 6.10^5 est 6.10^5+1 (on peut aussi avoir 0 cheveux )

    ​​


Log in to reply
 

Looks like your connection to Expii Forum was lost, please wait while we try to reconnect.