Question d'amitié — Les-mathematiques.net The most powerful custom community solution in the world

Question d'amitié

Modifié (November 2023) dans Combinatoire et Graphes
En visitant une ville de 20 bandits, Alice apprend que chacun de ces bandits est ami avec au moins 15 autres bandits de la ville. Quelle est la valeur maximale que peut prendre K si Alice peut toujours former un groupe de K personnes dans lequel deux membres quelconques sont amis l'un avec l'autre, quelles que soient leurs amitiés dans la ville ?
Mots clés:
«1

Réponses

  • Bonjour,
    C'est $K = 20$, non ?
  • Modifié (November 2023)
    Désolé, mauvaise réponse
  • Ben pourtant, dans le groupe de 20 bandits, il y a forcément deux membres qui sont amis par hypothèse.
  • Vérifiez à nouveau votre réponse, votre solution est fausse.
  • Tu peux m'indiquer la vraie solution alors ? Parce-qu'à part $K = 20$, je ne vois pas ce que cela pourrait être.
  • 6, c'est mieux ?
  • Mieux, mais la réponse n'est pas 6
  • Peux-tu écrire le problème en anglais puisque c'est ta langue d'origine ? Il me semble que la traduction est mauvaise, bien sûr avec la permission des modérateurs.
    Le 😄 Farceur


  • Modifié (November 2023)
    Fais-le toi-même gebrane : https://www.deepl.com/fr/translator
  • Bonjour,
    Sans l'habillage, je comprends le problème comme :
    Quel est le plus grand entier $k$ tel que tout graphe simple à 20 sommets où chaque sommet est de valence au moins 15 contienne un sous-graphe complet à $k$ sommets ?
  • Effectivement il y a un problème de traduction. Tel que je l'interprète, la réponse est $20$.
  • Chaurien dit "fais-le toi-même", il me semble que je n'ai pas sonné à ta porte !
    Et que devrais-je traduire ? Je n'ai pas la copie originale en anglais de la question.
    Le 😄 Farceur


  • Modifié (November 2023)
    Alice peut toujours former un groupe de K personnes dans lequel deux membres sont amis

    Comme le dit @GaBuZoMeu , on veut pouvoir former un groupe de $K$ personnes dans lequel deux membres quelconques sont amis.
    Enfin, je crois...

  • En visitant une ville de 20 bandits, Alice apprend que chacun de ces bandits est ami avec au moins 15 autres bandits de la ville. Quelle est la valeur maximale que peut prendre K si Alice peut toujours former un groupe de K personnes dans lequel deux membres quelconques sont amis l'un avec l'autre, quelles que soient leurs amitiés dans la ville ?
  • Pourquoi ne pas dire que c'est bien le problème de théorie des graphes que j'ai formulé ?
  • Oui, quelque chose comme ça
  • Quelle est votre solution pour cela ?
  • Quelque chose comme ça ou exactement ça ?
  • Si oui, à quoi trouvez-vous la réponse ?
  • Pas envie de chercher si je ne suis pas sûr de la question. J'attends une réponse claire.
  • Modifié (November 2023)
    La question est telle que je l'ai écrite.
  • Quel est ton but en te comportant de la sorte ? .
    Cherches-tu à poser une colle aux membres de ce forum, ou cherches-tu de l'aide ?
     Il vaut mieux rédiger ta propre réponse pour susciter l'intérêt de quelqu'un à te répondre
    Le 😄 Farceur


  • Modifié (November 2023)
    On considère ici un graphe sur $20$ sommets qui sont tous de degré au moins 15. On cherche le cardinal maximal d'une clique.
     Par la formule "somme des degrés $=$ $2$ fois le nombre d'arêtes", ce dernier vaut au moins $150$.
     On peut tenter un principe des tiroirs ...
  • Modifié (November 2023)
    Je partage les bonnes questions qui me viennent à l'esprit, au cas où il existerait des solutions différentes et meilleures, d'ailleurs, si vous êtes curieux, la réponse est 4.
  • Modifié (November 2023)
    L'existence d'une 4-clique est assurée par le théorème de Turán qui entraîne qu'un graphe à 20 sommets qui ne contient pas de 4-clique a un nombre d'arêtes majoré par $\left(1-\dfrac13\right) \dfrac{20^2}2$. Par ailleurs le graphe de Turán $K_{5,5,5,5}$ a 20 sommets chacun de valence 15 et aucune 5-clique.
  • Alors, comment le trouveriez-vous si je ne disais pas que la réponse était 4 ?
  • Modifié (November 2023)
    En connaissant le théorème de Turán qui dit que le nombre maximal d'arêtes d'un graphe à $n$ sommets qui ne contient pas de $r+1$-clique est réalisé par le graphe de Turán $T_{n,r}$, le graphe complet $r$-partite où les $n$ sommets sont partagés en $r$ parties indépendantes de la manière la plus équitable possible (chaque partie indépendante a $\lfloor n/r\rfloor$ ou $\lfloor n/r\rfloor+1$ éléments).
    $T_{20,3}$ a 133 arêtes, moins que 150.
  • Alors comment prouver que la réponse est 4 ?
  • Je l'ai prouvé en utilisant le théorème de Turán. Tu n'as pas compris ?
  • Pourriez-vous s'il vous plaît expliquer plus en détail ?
  • Je te laisse te renseigner sur le théorème de Turán et les graphes de Turán et réfléchir à ce que j'ai écrit. Bon travail !
  • Donc, tu poses des questions qui te viennent à l'esprit!
    Je reconnais que tu as posé une question très intéressante dans un récent fil, mais tu avais un résultat faux avec une preuve fausse.
    Tu as dû galérer pour nous présenter plusieurs tentatives fausses à ta question. Vers la fin, tu as réussi après avoir lu la mienne et surtout celle de Gabu. Maintenant, pour cette nouvelle question, soit on t'a soufflé le 4 ou tu as bien une preuve.
    Présente-nous ta preuve. 
    Le 😄 Farceur


  • Frère, je partage juste les questions qui me viennent à l'esprit, que je trouve bonnes, avec le forum pour que tout le monde puisse en bénéficier. As-tu un problème avec moi, je ne comprends pas ?
  • Modifié (November 2023)
    Je t'ai posé une question as-tu une preuve à ta propre question  ? (Le 4 ne peut pas venir du ciel)  Si oui partage cette solution. Dans ce forum, les conflits ne sont pas d'ordre  personnelles mais d'ordre mathématiques. 
    Le 😄 Farceur


  • La réponse à la question est 4 mais il n'y avait pas de solution
  • Modifié (November 2023)
    Vérifiez à nouveau votre réponse, votre solution est fausse.
    Désolé, mauvaise réponse
    Quand tu envoies des messages comme ça, on a l'impression d'avoir affaire à un examinateur un peu désagréable lors d'un oral. Or, tu sembles être juste un amateur de jolis problèmes (au passage, merci pour ces énoncés intéressants) dont tu ne comprends pas vraiment les solutions, ce qui n'est pas tout à fait la même chose.
    Il serait plus honnête de ta part d'envoyer le message suivant.

    Bonjour
    J'ai vu l'énoncé ci-joint dans la revue Mathématiques Rigolotes et sa réponse que je ne parviens pas à obtenir par moi-même.
    (.......)
    Sauriez-vous m'expliquer s'il vous plait comment aboutir à ce résultat.
    Un grand merci d'avance.
  • Je connais les problèmes et je comprends les solutions, mais je pense qu'il ne serait pas correct pour les autres personnes du forum qui veulent y réfléchir si j'écris la solution avec la question. Je pense qu'il est juste de poster la mienne ou solution officielle après vos solutions. Il faut savoir que si je ne comprends pas ou ne connais pas la solution, je n'hésiterai pas à vous dire que je ne comprends pas ou que je ne sais pas.
  • Modifié (November 2023)
    "je comprends les solutions"
    Très bien, tu vas donc pouvoir comprendre la démonstration que je t'ai donnée ici, une fois que tu auras bien compris l'énoncé du théorème de Turán et ce que sont les graphes de Turán.
  • Modifié (November 2023)
    La réponse à la question est 4 mais il n'y avait pas de solution
    Je connais les problèmes et je comprends les solutions
    Il faudrait savoir...
  • Le graphe de Turán $T_{20,4}=K_{5,5,5,5}$ a pour sommets les couples $(i,j)$ avec $i$ entier entre 1 et 4 et $j$ entier entre 1 et 5, ce qui fait 20 sommets. Il a une arête entre $(i,j)$ et $(k,\ell)$ si et seulement si $i\neq k$, ce qui fait 150 arêtes. Chacun de ses sommets est de valence 15. Il a 625 4-cliques et aucune 5-clique.
  • Modifié (November 2023)
    Bonjour @GaBuZoMeu
    Si on change le 20 par 10 et le 15 par 6, puis-je avoir une réponse.
    J'aimerais poser cette question à mon groupe d'ami(es).
    Le 😄 Farceur


  • Je te laisse y réfléchir. Si tu as lu la page wikipedia sur le théorème de Turán, tu as tout ce qu'il te faut. Je te conseille la page en anglais.
  • Si on change 20 par 10 et 15 par 6 on obtient 3 normalement.

    Pour les petites valeurs comme ici on peut également considérer "l'énoncé complémentaire" : traduire le problème à l'aide du graphe complémentaire. Par exemple ici ça donne : trouver le plus grand entier $k$ tel que tout graphe simple à 10 sommets où chaque sommet est de degré au plus 3 contienne un sous-graphe sans arêtes à $k$ sommets. On réduit ainsi le nombre d'arêtes et on trouve facilement de tête un exemple qui montre que le $k$ en question est $\leq 3$ (exemple : $G=K_4\sqcup K_4\sqcup K_2$). Puis on montre facilement qu'il vaut 3.
  • Modifié (November 2023)
    Merci raoul-s pour tes explications et ta réponse  3. Je vais essayer de la retrouver avec le théorème si je comprends quelques choses.
    Le 😄 Farceur


  • Ton graphe a 30 arêtes, le graphe de Turán $T_{10,3}$ en a 33 et le $T_{10,2}$ 25.
  • Pour le moment, je ne comprends rien à ce que tu dis. Je dois trouver du temps pour me familiariser avec les graphes et le théorème cité. Peux-tu me dire au moins si tu es d'accord avec la réponse de Raoul-s ?
    Le 😄 Farceur


  • Je suis d'accord pour le 3. Pour le reste, à toi de voir si tu peux mettre en oeuvre ses indications.
  • À quoi sert la théorie des graphes ? Est-ce que cette théorie est capable de résoudre une énigme d'un jeu de mon enfance ? Je jouais avec mes amis d'enfance à tracer ce dessin sur le sable sans lever le bras. Personne n'a réussi à le résoudre.

    Le 😄 Farceur


  • Modifié (November 2023)
    Bonjour Gebrane.
    S'il s'agit de tracer le dessin carré, aucun problème. Si les deux rectangles noirs font partie du tracé, impossible, c'est évident. Enfin, s'il s'agit de tracer le carré et ses traits intérieurs d'un seul trait sans repasser sur les traits déjà tracés, la théorie des graphes répond (voir graphes eulériens) : pas possible, il y a 4 > 2 sommets impairs.
    Cordialement.
    NB. C'est une des premières questions de topologie apparue historiquement ("ponts de Königzberg")
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!