Marathon de Combinatoire



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



  • @hamza-ba-mohammed said in Marathon de Combinatoire:

    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.

    d'abord il n'existe pas exactement une ligne differente de A dans B et C,mais au moins une telle ligne,d'autre part je ne vois pas pourquoi il y aura 10210^2 lignes differentes de A dans B et C dans ce tableau,car on nous a donné l'existence d'au moins une ligne,et non pas de toute les lignes,et puis tu as oublié le fait que c'est valable pour tout B et C et non pas pour 2 colonnes seulement



  • @abdellah-elmrini svp j ai pas compris pourquoi celui avec 46 est dans la meme equipe que celui avec 0


Log in to reply
 

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