Marathon de Combinatoire



  • Bonjour.
    La combinatoire incite à une bonne gymnastique de l'esprit. De plus, elle ne fait que peu appel à des résultats déjà connus. Les solutions sont souvent astucieuses et une fois l'idée de la démonstration dénichée, la résolution est rapide. Ce marathon sera donc, si vous vous en donnez à cœur joie, très fluide.
    En outre, les problèmes et les solutions ne requièrent pas du Latex pour être lisibles. Les caractères normaux du clavier suffisent.
    Les problèmes et les solutions doivent se suivre. Si quelqu'un qui répond à un problème n'a pas de nouveau problème à proposer, qu'il l'indique clairement ! D'autres s'en chargeront, si possible.
    Merci de :

    • Numéroter clairement les problèmes, et citer le numéro du problème dans la solution que l'on en donne.
    • Ne pas spoiler les solutions afin de ne pas biaiser l'esprit des participants.
    • Veiller à ne pas répéter les problèmes.
    • Expliciter les notations utilisées, si nécessaire
    • Ne pas indiquer les sources des problèmes pour éviter des cas de tricherie.
    • Poster de solutions meme incomplètes , l important étant de discuter et de construire un raisonnement.
    • Si au bout de 12 heures aucune solution n'a été donnée , celui qui a proposé le probleme doit proposer sa solution ( modulable selon la période )
      Je commence avec le premier problème proposé par Saad Choukri
      1- IMO 1972 P1
      0_1481578531255_P1.png


  • Solution du probleme 1- IMOIMO 19721972 P1P1
    Pour chaque sous ensemble de 10 élements on peut séléctionner 2101=10232^{10}-1=1023 sous ensembles distincts et non vide .
    Hors la somme des élements de XX est inférieure à 90+91+92....+99=94590+91+92....+99= 945
    Donc d apres le principe des tiroirs on aura deux sous ensembles distincts YY et ZZ dont la somme des éléments est égale.
    Remarquons alors que les sous ensembles YYXY-Y\cap X et XXYX-X\cap Y ont la meme somme et sont disjoints ce qui nous permet de conclure.
    CQFDCQFD


  • Math&Maroc

    @Mamoun Pourquoi as-tu publié ta solution aussi vite? Cela ne fait que 11 minutes que ton problème a été proposé!



  • Non ca fait 3 heures que ce probleme a été proposé par Choukri Saad . J ai voulu le prendre comme exemple pour entamer ce marathon et j ai résolu l exercice et à mon tour je poste le mien . A savoir que on aimerait que ce marathon soit le plus fluide possible donc ce n est pas dérangeant si les soluttions soient postés apres un courrt laps de temps ( par un autre que celui qui a proposé le probleme bien sur )


  • Math&Maroc

    @Mamoun Je n'avais pas compris que tu reprenais un problème posté par une autre personne.

    Bon marathon dans ce cas :D



  • Probleme 2 :
    On place au hasard 99 carrés d aire 15\frac{1}{5} à l'intérieure d'une figure FF d'aire 11
    Prouver qu il existe au moins deux carrés dont l intersection a une aire 145\geq \frac{1}{45}



  • Supposons par absurde que tous deux carrés ont une intersection strict.inferieure à 145\frac{1}{45} donc au total , puisque on a 36 pairs de carrés la somme des surfaces de toutes les intersections sera inferieure à 3645=45\frac{36}{45} = \frac{4}{5} mais ceci ne peut pas etre vrai puisque la surface totale des carrés est 95\frac{9}{5} et( donc la somme des intersections doit etre superieur à 951=45 \frac{9}{5} - 1 = \frac{4}{5} )



  • @Abdellah-Elmrini Tres bien juste n oublie pas de preciser le strictement à chaque étape!
    A ton tour de poster



  • Problem 3 :
    There are 2009 clubs, each with 45 members, any two of which have exactly one person in common. Show that there is one person who is a member of all the clubs.



  • @Abdellah-Elmrini
    Supposons le contraire
    Prenons un club C1C_1 il a 4545 membres donc d apres le principe des tiroirs et les conditions de l exercice il a 1 membre qui appartient à au moins 4545 autres clubs qu on note C2,C3....C46C_2,C_3....C_{46} . Donc on a 4646 clubs avec le meme membre en commun qu on appelle Mamoun :p
    Prenons un autre club CkC_k
    Il a un membre en commun avec chacun des 46 clubs C1,C2....,C46C_1,C_2....,C_{46}
    Donc il a un membre en commun avec au moins deux d'entre eux et d apres les conditions de l exercice ce ne peut etre que Mamoun.
    On réitère le même raisonnement pour en déduire que Mamoun appartient à tous les clubs.
    CQFDCQFD



  • Probleme 4:
    Dans une compétition mathématique il y a 2424 équipes participantes . Chaque équipe est présidée par un leaderleader et un deputydeputy leaderleader . Au début de la réunion d'organisation quelques chefs de délégations (leaders et deputy leaders) se serrent la main , les deux chefs d'une meme equipe ne se serrent pas la main. A la fin de la réunion, un leader L demande aux 47 autres personnes le nombres de poignées qu ils ont faites et toutes les réponses étaient différentes. Combien de personnes ont serré la main du deputy leader ( le collegue du leader LL) ?



  • Puisque le nombre de poignees peut varier entre 0 et 46 celui avec 46 et celui avec 0 doivent etre dans le meme team, on peut negliger ce couple et considerer le reste , de la meme demarche necessairement celui avec 1 doit etre avec celui avec 45, on continue jusqu'a ne plus avoir que le nombre 23 , et c'est exactement le nombre de poingnes recherché .



  • Problem 5
    If nn people are seated in n+k n +k chairs in a row ( n1k1 n-1\geq k \geq 1 ), then there always exists a row of mm people
    For a given k what's the maximum value of mm ?



  • Traduction
    Si nn personne sont assis sur n+kn+k chaises en formant une ligne , alors il va toujours exister une succession de m personnes
    Pour un k donné quelle est la valeur maximale que m peut atteindre ?.



  • On considere les k places vides , ils nous repartissent les n personnes en k+1 groupes et puis le principe des tiroirs nous donne que il y a au moins un groupe avec E(nk+1)+1 E(\frac{n}{k+1})+1 personnes qui est notre mm



  • Problem 6
    Two bored millionaires, Bilion and Trilion, decide to play a game. They each have a sufficient supply
    of {$1, {$2, $5, and $10 bills. Starting with Bilion, they take turns putting one of the bills they have into
    a pile. The game ends when the bills in the pile total exactly $1,000,000, and whoever makes the last
    move wins the $1,000,000 in the pile (if the pile is worth more than $1,000,000 after a move, then the
    person who made the last move loses instead, and the other person wins the amount of cash in the
    pile). Assuming optimal play, how many dollars will the winning player gain?



  • Je ne vais pas donner une solution complete, mais plutot des pistes pour ceux qui voudraient travailler l exercice car il est tres interessant.
    11- Montrer premierement qu un joueur AA a une stratégie gagnante ( penser à travailler modulo )
    22- Etudier le mouvement optimale du joueur BB pour qu il perde le moins d argent possible (en sachant que dans tous les cas il perd)
    Je mettrais une solution complete demain soir si personne ne s en charge



  • Exercice 7:
    1-Deux amis jouent à un jeu . Ils prennent le nombre 10011001 à chaque étape ils ont le choix de retrancher de ce nombre un nombre compris entre 11 et 77 . Celui qui gagne est celui qui fait arriver le nombre à 00
    Montrer que l un des joueurs à une stratégie gagnante et préciser lequel.
    2- Remplacer 10011001 par 2325 2325 et 77 par 3030 et répondre à la meme question
    3- Généraliser le probleme pour nn à la place de 10011001 et pp<nn a la place de 77



  • Soit rr le reste de nn modulo p+1p+1, clairement rr est choisissable , le joueur 1 le choisit en premier et s'assure de garder le nombre restant toujours congru à rr mod p+1p+1. Il a donc toujours la strategie gagnante



  • Problem 8
    Soit M un sous-ensemble de { 1, 2, 3, . . . , 15 } tq le produit de tout trois elements distincts
    de M n'est pas un carre . Determiner le nombre maximal des elements de M


Log in to reply
 

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