Exercice 2



  • n3n \geq 3 couples mariés suspectés de porter une maladie contagieuse, sont mis dans une quarantaine qui contient deux grandes tables. Ils sont assis à ces deux tables de telle maniére qu'aucune personne n'assis à la meme table que son époux/eoupse. Il n'ont pas le droit de changer leurs places après.

    Initiallement, aa des invités vraiment portent la maladie contagieuse. Pour toute personne PP, on considère les deux personnes adjacentes à PP, plus son epoux/epouse. Chaque jour, si au moins deux parmi ces trois personnes sont malades, PP devient malade aussi, et ne pourra jamais se retablir.

    quelle est la valeur minimale de aa, pour que tout le monde portera la maladie et qui marche peu importe la manière dont les couples sont assis ?



  • Est ce que le meme nombre de personnes est assis à chaque table?



  • Si tu y penses un peu, tu auras la reponse tout seul. :stuck_out_tongue_winking_eye:



  • Ah oui c'est vrai !



  • La réponse est 2n32n-3
    Montrons premierement qu il y a nn personnes assises à chaque table Supposons le contraire donc il existe une tabble avec n+1n+1 personnes donc une femme est assise à la meme table que son mari . Absurde!
    Donc chaque table contient n personnes.
    Si aa remplit les conditions de l exercice donc a+1a+1 également.
    On va donc démontrer que a=2n4 a=2n-4 ne fonctionne pas pour déduire que a>2n4a \gt 2n-4
    Pour 2n42n-4 On choisit de mettre n2n-2 personnes contaminés à chaque table tel que les deux personne non contaminés complètent le cercle formé par les personnes contaminés et que ces deux personnes se trouvent cote à cote . C'est à dire que chacun de ces personnes ait l autre personne non contaminé comme adjacent et une personne contaminée. On fait de meme dans l autre table et on considere que les deux personnes non contaminés du premier groupe sont mariés avec les deux personnes non contaminées du deuxieme groupe. Donc aucune des conditions des transmissiosn de la maladie n'est satisfaite .
    Donc a>2n4 a \gt 2n-4
    Montrons que a=2n3a=2n-3 fonctionne. D après le principe des tiroirs une table qu on note t1 t_{1} contient au moins n1n-1 personnes contaminés . Donc d apres les conditions de l exercice cette table verra tous ses membres contaminés.
    Considérons la table t2 t_{2} Elle contient au moins n3n-3 personnes contaminées. Donc il reste 3 personnes non contaminées. Au moins 22 de ces personnes ont une personne contaminée adjacente et comme dans la table t1 t_{1} tout le monde est contaminé
    Alors ces deux personne seront contaminés à leur tour alors t2 t_{2} contient n1 n-1 personnes contaminées Donc toutes les personnes deviendront contaminées.
    En conclusion min(a)=2n3min(a)=2n-3


Log in to reply
 

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