[Cours premier] Invitation aux debutants.


  • Math&Maroc

    Bonjour!

    Avec l'equipe pedagogique de l'association Maths & Maroc, nous avons decider d'organiser un mini-workshop pour but de vous assister a faire votre premier pas vers les combinatoires; un sujet incontournable pour votre preparation aux olympiades nationales et internationales. Ayant destine ce mini-workshop aux debutants d'entre vous, nous choisissons comme reference alors, l'excellent cours sur les strategies de base, redige par l'association Animath. Ce cours est telechargeable gratuitement depuis leurs site-web que je cite pour vous: http://www.animath.fr/

    L'article en question est le suivant: http://www.animath.fr/IMG/pdf/cours-base.pdf

    Vous etes alors invite a lire ce cours en details et a faire les exercices y figurants. Le deuxieme poste de ce sujet contiendra l'ennonce du premier probleme, et vous etes alors invites a proposer vos solutions. Une fois un probleme est resolue, nous (moi ou l'un des autres moderateurs) posterons le probleme qui suit, que vous etes alors invites a resoudre, et ainsi de suite.

    Ce mini-workshop est alors votre chance ideale pour apprendre quelques astuces utiles pour faire des combinatoires.

    Avant de commencer, j'aimerais instaurer quelques regles organisationnelles:

    1- Si vous etes avances en combinatoire (i.e si vous arrivez a faire tout les exercices sans difficulte), ce mini-workshop n'est malheureusement pas pour vous, mais vous etes par contre toujours invite a commenter, corriger ou bien completer les solutions des autres membres.

    2- Pour laisser la chance a tous le monde de participer, ne soyez pas le premier a poster vos solutions a trois problemes consecutifs. Par exemple, si vous etes le premier a poster une solution aux exercices 2 et 3, vous deverez attendre quelqu'un a resoudre le probleme 4, avant de poster votre solution.

    3- Ne jamais poster une solution a un probleme que les moderateurs n'ont pas encore propose. Par exemple, ne postez pas une solution au probleme 6, alors que la discussion est encore sur le probleme 4 ou 5.

    Ces regles doivent mettre en evidence le but principal de cet effort: Inviter les debutants a resoudre leurs premiers exercices de combinatoires et a apprendre quelques techniques qui leurs seront utiles pour les olympiades a venir.

    Bonne chance a tous.


  • Math&Maroc

    Exercice 1:

    Paris compte deux millions d'habitants. Un etre humain a, au plus, 600000 cheveux sur la tete. Combien de Parisiens peut-on trouver qui ont exactement le meme nombre de cheveux sur la tete?



  • Soit n le nombres des parisiens et k le nombre de cheveux possible alors au moins un nombre de cheveux compris entre 00 et 6.1056.10^5 sur la tete de 4 personnes car [2.1066.105+1][\frac{2.10^6}{6.10^5+1}]=4


  • Math&Maroc

    Très bien Taha.
    Exercice 2:
    On a jeté de la peinture noir sur le sol blanc d'une pièce carrée de 2 mètres sur 2, n'importe comment. Montrez qu'il existe deux points de la même couleur dont la distance est exactement un mètre.

    N’hésitez pas à poser des questions! C'est le but ;)


  • Math&Maroc

    Indice: Penser a un triangle equilateral de cote 1, inclut entierement dans ce carre.



  • donc au moins deux sommets en meme couleur dont la distance est 1 mais je pense qu'on peut avoir autres mesures comme 1.5 ou 0.5 mètre c possible ?



  • @Tähä-Britäl En effet. Une question ouverte : Quel est la meilleur constante par laquelle on peut remplacer notre 1 ?


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