Un loup et cinquante moutons

par **Imod** » 29 Oct 2010, 16:47

Une énigme pour :zen:

Dans le plan vivent un loup et cinquante moutons . A tour de rôle , le loup puis un mouton se déplacent d'au plus un mètre dans une direction librement choisie . S'il agît au mieux le loup pourra-t-il toujours attraper au moins un mouton quelle que soit la position initiale et la stratégie des moutons ?

Amusez-vous bien :lol3:

Imod

par **Doraki** » 29 Oct 2010, 17:27

Le loup n'a pas le droit de se déplacer de moins de 1m, et s'il n'est pas EXACTEMENT sur un mouton, ça ne compte pas, c'est ça ?

par **Imod** » 29 Oct 2010, 17:35

Non au plus un mètre , j'ai corrigé le message initial .

Imod

par **beagle** » 29 Oct 2010, 17:37

non, dans la vraie vie, comme dans cet exo réaliste, le loup qui est à 80cm ou 52cm d'un mouton, si c'est son tour il le bouffe,
sinon cela s'appelle saute-mouton, jeu moins cruel ...

zut alors imod dit comme doraki, à mon avis c'est pour mathématisé encore plus la difficulté du loup,cela va l'énerver encore plus.

par **Imod** » 29 Oct 2010, 17:45

En fait le loup et l'un des moutons se déplacent d'au plus un mètre à chaque tour .

Ah si je pouvais éditer :cry:

Imod

par **nodjim** » 29 Oct 2010, 18:34

Je dirais que si un mouton fuit en ligne droite, il ne peut être atteint.

par **Sve@r** » 29 Oct 2010, 18:36

Ca me rappelle un jeu "robots". On dirige un petit bonhomme qui peut se déplacer d'une case dans les 8 directions. Et on est poursuivis par des robots qui ont la même possibilité.

Ben en fait, on peut pas échapper aux robots. Heureusement que quand 2 robots se touchent ils s'annihilent.

Et donc là c'est pareil.

Maintenant, un discours un peu plus mathématique: Imaginons un mouton situé à une distance d du loup. On trace donc une ligne droite reliant le mouton et le loup. Seul un déplacement dans le prolongement de cette ligne l'écarte du loup. Tout autre déplacement permet au loup de réduire la distance. Et comme à un moment donné il y a le bord du terrain...

par **nodjim** » 29 Oct 2010, 18:41

Imod ne dit pas que le plan est limité.

par **nodjim** » 29 Oct 2010, 19:00

Ah oui, je n'avais pas bien lu: un seul mouton à la fois se déplace; ça change tout.

par **nodjim** » 29 Oct 2010, 19:07

Ah oui, je n'avais pas bien lu: un seul mouton à la fois se déplace; ça change tout.

par **Sve@r** » 29 Oct 2010, 20:35

nodjim a écrit:Imod ne dit pas que le plan est limité.

Exact. J'ai présumé à tort.

nodjim a écrit:Ah oui, je n'avais pas bien lu: un seul mouton à la fois se déplace; ça change tout.

Pas forcément. Il suffit que ce soit le mouton le plus proche du loup qui se déplace dans la direction opposée...

par **Imod** » 29 Oct 2010, 20:50

Sve@r a écrit:. Il suffit que ce soit le mouton le plus proche du loup qui se déplace dans la direction opposée...

Mais il peut alors se rapprocher de l'un de ses congénères et le coup suivant le loup aura deux moutons dans son disque d'action et là ça fait mal :zen:

Je reviens , tout à l'heure ( j'ai du monde à la maison :zen: )

Imod

par **nodjim** » 29 Oct 2010, 20:53

D'accord mais il n'y a pas qu'un seul mouton. Imagine qu'il vise des moutons alignés, et ça arrive tôt ou tard.
Aussi je soupçonne une stratégie en rabatteur, genre une spirale rentrante autour d'un groupe. Reste que le loup devra bien laisser filer qq individus. Faudrait se mettre en fait à la place de l'ensemble des moutons, car s'ils perdent un seul des leurs, ils ont perdu.

par **ffpower** » 29 Oct 2010, 21:09

Moi je soupconnerai un invariant a faire diminuer..
En tout cas s'il y a que 4 moutons, le loup peut pas s'en sortir..mais ce serait étonnant que 50 soit optimal

par **Ben314** » 29 Oct 2010, 23:51

Bon, j'ai rien trouvé.... :cry:

(pour le moment) mais, comme j'aime bien causer quand j'ai rien à dire, je précise que :

Je trouve ça bien beau comme énigme
Je vais me coucher convaincu que le loup étant plus malin que moi finira forcément par attraper un des moutons...

par **Imod** » 29 Oct 2010, 23:57

La solution est d'une simplicité confondante , mais bonne nuit quand même :ptdr:

Imod

par **Sve@r** » 30 Oct 2010, 00:04

Imod a écrit:Mais il peut alors se rapprocher de l'un de ses congénères et le coup suivant le loup aura deux moutons dans son disque d'action et là ça fait mal :zen:

Mouais. C'est vrai que si un seul mouton se déplace et que le loup en cible 2 alignés, il devrait en choper un des deux.

Mais imaginons une position à peu près neutre ; le loup n'étant à proximité immédiate d'aucun mouton. Au premier mouvement qu'il fait, un premier mouton se sentant visé envisagera alors la direction opposée... sauf si cela le met directement en alignement avec un de ses congénères. Dans ce cas, il choisit une direction un peu divergente. Ok la direction n'étant pas parfaitement opposée, le loup réduit un peu la distance mais pas énormément. Et dans les coups suivants, les deux moutons étant dans des directions divergentes s'écarteront l'un de l'autre. Le loup ne pourra pas poursuivre les deux à la fois...

nodjim a écrit:Aussi je soupçonne une stratégie en rabatteur, genre une spirale rentrante autour d'un groupe.

Le principe des rabatteurs c'est qu'ils sont plusieurs pour que le gibier ne puisse aller que dans une direction. Là, avec un seul loup, je le vois bien tourner comme un gland pendant que le groupe s'égaille dans des directions opposées divergentes.

C'est un truc que j'aimerais bien programmer en simulation...

par **ffpower** » 30 Oct 2010, 00:07

Ca pourrait faire un jeu flash sympa :)

par **Imod** » 30 Oct 2010, 00:11

Vous faîtes peur les gars , on pourrait aussi imaginer un dragueur cherchant sa cible , va-t-il finir la nuit seul ????

Allez , bonne nuit :ptdr:

Imod

par **Doraki** » 30 Oct 2010, 08:24

J'ai une solution pas trop compliquée. Le loup n'attrapera jamais de mouton.

Un loup et cinquante moutons

Un loup et cinquante moutons

Qui est en ligne