Marathon de Combinatoire



  • 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



  • @Abdellah-Elmrini said in Marathon de Combinatoire:

    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

    Si p+1rp+1|r on aura rr n est pas choisissable et c est le joueur 2 qui gagne dans ce cas . C est le cas deuxieme question de l exercice.
    On a donc également généralise le probleme^^^



  • This post is deleted!


  • Considérons les triplets (1,4,9)(2,7,14)(5,15,12)(3,6,8)(1,4,9)(2,7,14)(5,15,12)(3,6,8)
    Le principe des tirois nous dit que Card(M)11Card(M)\leq 11
    Essayons de construire un ensemble à 11 elements.
    Si l un des nombres (10,11,13)(10,11,13) n appartiennent pas à MM alors Card(M)10Card(M)\leq 10 et on a fini.
    Donc (10,11,13)(10,11,13) appartiennent à MM
    On doit puiser deux élements exactement dans chacun des triplets que l on a selectionné.
    (5,2)(5,2) ne peuvent pas appartenir simultanément à l ensemble (5.2.10=1025.2.10=10^2)
    (5,8)(5,8) aussi (5.8.10=2025.8.10=20^2)
    (5,3,15)(5,3,15) aussi (5.3.15=1525.3.15=15^2)
    Si 55 appartient à MM alors (6,3)( 6,3) aussi. On aura donc 1212 appartient à M. Donc 1515 n appartient pas à MM
    Alors 44 n appartient pas à MM
    Donc notre MM sera 1,3,5,6,7,9,10,11,12,13,141,3,5,6,7,9,10,11,12,13,14 Hors 12.3.1=36=6212.3.1=36=6^2
    Absurde!
    Donc 5 5 n appartient pas à MM
    Donc 33 n appartient pas à MM Donc (6,8)(6,8) appartiennent à MM
    Donc 22 n appartient pas à MM
    Donc notre MM sera 7,14,15,12,6,8,10,11,137,14,15,12,6,8,10,11,13 + deux elements de (1,4,9)(1,4,9) Hors 15.6.10=900=30215.6.10=900=30^2 Absurde!
    Donc card(M)10card(M)\leq 10
    M=1,3,4,5,6,7,10,11,13,14 M={1,3,4,5,6,7,10,11,13,14} est un exemple de solution à 10 élements



  • Probleme 9
    0_1481758043735_S1.png



  • Montrer que nn est pair
    Montrer que n2=8k+1n^2=8k+1 en utilisant une coloration adequate pour en deduire que n=4k+2n=4k'+2
    Puis donner une configuration adéquate



  • Allez hop il temps que cette discussion revienne à la vie! Je commence en proposant une sol au probleme de Mamoun(ça date quand meme !)
    Probleme 9
    on a chaque Tetromino couvre exactement 44 cases,donc il est clair que nn est pair,on a donc 2 cas, n=4k+2n=4k+2 et n=4kn=4k
    Cas 1: n=4k+2n=4k+2
    Simple!il suffit de n'utiliser que des Square-Tetrominos
    Cas 2 n=4kn=4k
    Supposons qu'il existe un n=4kn=4k pour lequel ...(blablabla,l'enoncé du problème),soit ss le nb de Square-tetrominos qu'on a utilisé pour faire un tel recouvrement,et tt le nb de T-tetrominos,ss est impair et 4s+4t=16k4s+4t=16k donc tt est egalement impair,colorions l'echiquier par un coloriage Black-White standard,notons BB le nb de cases noires et WW le nb de cases blanches, clairement B=W=8kB=W=8k,là il suffit de remarquer que chaque Square-tetromino couvre le meme nombre de cases blanches que de cases noires,et chaque T tromino couvre 33 cases noire et 11 blanche ou vice versa,en notant xx le nb de T-tetrominos couvrant 3 cases blanches et yy le nb de T-tetrominos couvrans 3 cases noires ,on a 3x+y+2s=3y+x+2s=8k3x+y+2s=3y+x+2s=8k et t=x+yt=x+y,absurde car on trouve t=2x=2yt=2x=2y pair



  • Probleme 10
    Un tableau consiste de nn lignes et 1010 colonnes, chaque case contient un chiffre(de 00 à 99),suppsons que pour toute lignes AA et colonnes BB et CCil existe une ligne qui differe de AA exactement dans les colonnes BB et CC,mq nn>511511



  • Bonjour @Elias-Kaichouh ! J'ai voulu mettre un coup d'œil ici même que je sais que c'est élevé pour mon niveau mais bon 😅
    Pour ton dernier exercice je propose ce qui suit:
    Nous avons n lignes et 10 colonnes et chaque case contient un nombre de 0 à 9.
    Pour chaque ligne il existe une seule autre ligne différente d'elle dans les colonnes B et C.
    Il existera exactement 10210^2 modèles de lignes différentes dans les colonnes B et C.
    Donc il y aura au maximum 200 lignes respectant les deux conditions.
    Je me demande ce que j'ai raté dans mon raisonnement.


Log in to reply
 

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