On ne montre pas du doigt

[Imod]

Une petite énigme qui ne va pas vous résister :id:

On considère un groupe de personnes tel que chacun d'entre eux montre quelqu'un du doigt ( pas de narcissique à bord ) . Peut-on faire trois groupes de ces malpolis de façon à ce qu'aucun ne désigne un membre de son propre groupe ?

Bon courage !

Imod

[nodjim]

Il y a une infinité de cas où ça marche, il me semble, non ? :doh:

[fatal_error]

salut,

je pense qu'il faut (montrer ou pas) que qqsoit la facon dont se pointent les gens, on peut former trois groupes.

[melreg]

Je pense que c'est possible. Et voilà une esquisse de comment je procéderais...

Cadre général: on définit la "relation", notée ->, signifiant "pointe vers". On utilise cette "relation" pour passer d'une personne à une autre: par exemple, on choisit une personne, puis on va vers la personne qu'elle pointe, puis vers celle que cette dernière pointe, ....

Supposons qu'il y a n personnes,.
1) On remarque que si 1->2->3->...->n->1, alors on peut former trois groupes. En fait, si n est pair, deux groupes suffisent:
groupe 1: 1, 3, 5, ..., n-1
groupe 2: 2, 4, 6, ..., n
alors que si n est impair, il en faut 3: par exemple,
groupe 1: 1, 3, 5, ..., n-2
groupe 2: 2, 4, 6, ..., n-1
groupe 3: n

2) Si on a plusieurs boucles disjointes (par exemple, pour 2 boucles, 1->2->...->k->1 et k+1->k+2->...->n->k+1, 2 on forme trois groupes avec la premières boucle, puis on met (de la même manière) les personnes de la seconde boucle dans les trois premiers groupes (pas de problèmes car pas d'interaction entre les deux boucles).

3) On ne faite plus l'hypothèse fait sous 1) ni 2). On remarque que, partant d'une personne, on arrive forcément sur une "boucle" qu'on peut numéroter 1->2->...->k->1, . Par 1), on peut déjà former trois groupes (au plus) avec les personnes 1 à k (en respectant la règle demandée bien sûr). Ensuite, on fait le chemin inverse: on prend chaque élément de la boucle et on en ressort (i. e. on passe de la personne j de la boucle à la personne k+1 (numérotation qui ne nuit pas à la généralité) qui pointe vers j, puis à k+2 qui pointe vers k+1, ... ). On met k+1 dans un autre groupe que j, puis k+2 dans le groupe de j, et ainsi de suite jusqu'à arriver à une personne qui n'est pas pointée du doigt (possible car sinon, on n'a qu'une boucle, i. e. qu'on est dans le cas 1) ).

Je crois qu'il n'y a pas d'autres possibilités... Vous en pensez quoi?

PS: au fait, le mot d'ordre du forum est de ne pas donner de solution... mais est-ce que cette règle est valable ici aussi (étant donné que ce n'est pas (souvent) des exercices)? Si c'est le cas, désolé de ma réponse, les modérateurs peuvent l'éditer!

[nodjim]

Oui Melreg, tu peux donner les réponses. Attention tout de même aux petits malins qui viennent parfois proposer des enigmes qui sont en fait des problèmes de cours.
Cette enigme là n'est pas difficile, en général, ça l'est bien davantage.
Sinon, la représentation en graphe donne immédiatement ou presque la solution. Je pense que tu peux faire plus concis.

[nodjim]

Oh là là c'est quoi ces horaires décalés ? :cry: :cry:
Avant hier pas moyen de se connecter, il a dû y avoir un sacré bug. Apparemment tout n'est pas revenu dans l'ordre.
Bon courage aux administrateurs.:arf: :arf: :arf:

[Timothé Lefebvre]

Bonjour,

ton message n'est pas du tout hors charte melreg, tout le monde sait qu'Imod ne poste pas des énigmes dans le but d'en obtenir des réponses rapides parce qu'il ne les a pas ;)

[Imod]

Pour melreg >

Je ne vois pas trop comment tu traites le cas d'un individu montré du doigt par plusieurs ( disons un dizaine ) d'individus .

Il y a une réponse simplissime et limpide en quelques lignes :zen:

Imod

PS : Comme le dit Timothé ton message n'est pas hors charte , les problèmes que je propose sont simplement ceux qui me plaisent et que je veux partager ( rien à voir avec un travail scolaire ) :zen:

[melreg]

Merci à ceux qui m'ont répondu concernant la "légalité" de ma réponse. Et en effet, j'ai déjà vu suffisamment de messages d'Imod pour savoir que c'est ici, vraiment des énigmes.

@ nodjim: je me doute que la théorie des graphes est efficace pour un tel problème.

@ Imod:
1) Est-ce que la solution sur 3 lignes vient de la théorie des graphes justement? Ou bien, j'envisage même que ça peut être le genre de problème qu'un élève de début de lycée peut résoudre... non?
2) Concernant le cas où un individu est pointé du doigt par 10 personnes, j'ai tenté (vainement?) de l'expliquer quand je disais:

on fait le chemin inverse: on prend chaque élément de la boucle et on en ressort (i. e. on passe de la personne j de la boucle à la personne k+1 (numérotation qui ne nuit pas à la généralité) qui pointe vers j, puis à k+2 qui pointe vers k+1, ... ). On met k+1 dans un autre groupe que j, puis k+2 dans le groupe de j, et ainsi de suite jusqu'à arriver à une personne qui n'est pas pointée du doigt (possible car sinon, on n'a qu'une boucle, i. e. qu'on est dans le cas 1) )

En fait, si la personne visée par les 10 impolis est, disons, dans le groupe 1, on met tout ceux qui la pointe directement (=ceux à distance 1, si tu vois ce que je veux dire) dans le groupe 2, ceux à distance 2 dans le groupe 3, ceux à distance 3 dans le groupe 1, ...
Il me semble que comme ça, il n'y a pas de problèmes...

Remarque, je suis intéressé sur la solution concise... je m'y penche!

[Imod]

Est-ce que la solution sur 3 lignes vient de la théorie des graphes justement? Ou bien, j'envisage même que ça peut être le genre de problème qu'un élève de début de lycée peut résoudre... non?

Pas théorie des graphes juste un petit résultat de bon sens mais une méthode de démonstration plutôt étudiée en terminale qu'en début de lycée .

Imod

[lapras]

bonjour,
je pense que par récurrence c'est immédiat.

[Doraki]

Pour tout ensemble de n personnes dont certaines pointent du doigt quelqu'un d'autre dans l'ensemble, on peut le partager en 3 groupes tels que personne ne pointe une personne du même groupe.

Si n = 0, c'est facile.
Si n>0, il existe une personne A pointée par au plus 1 personne.
(il est impossible que tout le monde soit pointé par 2 personnes ou plus car 2n > n).
On écarte A de l'ensemble et on résout le problème pour les personnes restantes.
A peut pointer quelqu'un et A peut se faire pointer par quelqu'un, ce qui élimine au plus deux groupes.
Comme on dispose de 3 groupes on peut en trouver un qui marche pour y mettre A.

[lapras]

Ok j'ai exactement la meme chose.

[nodjim]

Avec les graphes:
Le graphe type, c'est une boucle de n personnes, d'où obligation de 3 groupes si n impair.
Chaque personne de cette boucle peut être pointée par d'autres personnes, et elles mêmes également, mais alors c'est un graphe exclusivement concentrique sans bouclage.
Une fois ce ou ces graphe(s) tracé(s), il est évident qu'on peut classer chacun des sommets avec seulement 3 groupes.

[Imod]

J'avais aussi fait une récurrence :we:

Imod