Forum de mathématiques - Bibm@th.net

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Sauter pour revenir, ou continuer...

Bonjour,

Voici un insecte sauteur au pied d'un mur vertical. Pour son premier saut, dans une direction perpendiculaire au mur, il a la force de parcourir une distance horizontale de N unités (N entier et supérieur à 8).
Sa force décline à chacun des sauts, toujours effectués perpendiculairement au mur, de sorte que chaque distance parcourue diminue d'une unité par rapport à la distance parcourue par le saut juste précédent.

S'il se rapproche du mur de départ, il ne peut s'y cogner pendant le saut, sous peine de se détruire.
S'il s'éloigne du mur de départ, il doit rester à une distance inférieure à 3xN du mur de départ, sous peine de ne plus distinguer son point de départ et d'errer indéfiniment...

Quel est le minimum de sauts qu'il doit faire, fonction de N entier supérieur à 8, soit pour revenir à son point de départ, soit pour se retrouver, avec une force amoindrie, comme lors de son premier saut, c'est-à-dire  à une distance X du mur de départ avec une force de X-1 pour le saut suivant.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Sauter pour revenir, ou continuer...

Salut,

sous réserve d'avoir tout bien compris, je tente une réponse.

La distance totale en p jump est égale à [tex]D(p)=p\times N - \frac{p(p-1)}{2}[/tex].

Le premier cas revient à résoudre [tex]D(p)=0[/tex], et le second, à [tex]D(p)=N[/tex], soit :

1 - [tex]p=2\times N+1[/tex]

2 - [tex]p=2\times N[/tex]

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : Sauter pour revenir, ou continuer...

Bonjour,

Il n'est pas si facile de trouver un bon mode de raisonnement pour un problème de minimum.
L'idée de cet insecte sauteur dont les forces déclinent est tirée d'un problème déjà posé différemment sur ce forum

Un exemple pour N=18 au premier saut, la force restante est 17 (soit N-1)
ensuite les sauts sont : -17, +16,  +15,  +14,  -13,  -12,  -11, -10 Soit 8 sauts après le premier saut pour revenir à son point de départ X=0.

Autre exemple pour N=19 au premier saut, la force restante est 18 (soit N-1)
ensuite les sauts sont : +18, -17, +16, +15, -14, -13, -12 soit 7 sauts pour arriver en X=12 avec une force restante de 11 (soit X-1)

Cordialement

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Sauter pour revenir, ou continuer...

Salut,

je n'avais pas imaginé que la puce était douée d'intelligence et qu'elle savait ce qu'elle voulait obtenir.

Cher ami, je crois que je rencontre avec vous un vrai problème de communication.
Ce doit venir sûrement de moi. Amen !

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : Sauter pour revenir, ou continuer...

Bonsoir,

@freddy :
Voilà un problème dont la solution, difficile elle aussi, mérite certainement d'être aussi recherchée…

Cordialement

karlun

Membre

Inscription : 05-05-2010

Messages : 216

Re : Sauter pour revenir, ou continuer...

Salut,

Sautons!
Donc, la puce, motivée de ne pas trop s'éloigner, sous peine d'errer, du mur du pied duquel elle commence une aventure, ne peut que sauter positivement; ensuite elle a le choix.

Pratique, muni que de mes +- (j'adore) et avec l'aide d'un (bête) tableur j'accroche des solutions du genre:

N=9 =>   +-+-+--  = 7 sauts:
(A lire: 9-8+7-6+5-4-3 = 0)

N=9 =>  +-++----  = 8 sauts

N=10 =>   ++-+----  = 8 sauts
N=10 =>   +++------  = 9 sauts

N=11 =>   ++--+--  = 7 sauts
N=11 =>   +-++----  = 7 sauts
N=11 =>   +++-----  = 8 sauts

N=13 =>   ++-+---  = 7 sauts

N=15 =>   +++----  = 7 sauts

N=...

(Pour ce qui est  X=-1 je regarde.)

7 serait-il le minimum recherché?
Comment raisonner?
Bof!

A+-*/

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : Sauter pour revenir, ou continuer...

Bonjour,

@karlun : la première approche est bien d'observer ce qui se passe pour des petites valeurs de N
Il y a mieux que le tableur pour cela, car, pour N donné, il faut trouver la "profondeur" minimale dans "l'arbre" des sauts. Une liste des valeurs atteintes à chaque profondeur est donc le bon moyen. Ci-dessous un outil simple programmé sous PYTHON.

On constate alors une certaine régularité (très surprenante) dans les minima obtenus pour des valeurs successives de N : On démontre ensuite que cette régularité est valable pour tout N...
Cordialement

#Python 3.2
#Sauts avec force diminuant de 1 à chaque saut
def sauter(nb,force,liste,N):
    newliste=[]
    for i in liste:
        if i==force:
            print("Saut début =",N, " :",nb, " sauts pour revenir à 0")
            return 0
        elif i==force+1 and nb>1:
            print("Saut début =",N, " :",nb, " sauts pour être comme après le 1er saut")
            return 0
        else:
            if i>force:
                if not i-force in liste:newliste.append(i-force)
            if i+force<=3*N:
                if not i+force in liste:newliste.append(i+force)
    sauter(nb+1,force-1,newliste,N)
for s in range(9,45):
    L=[s]
    sauter(1,s-1,L,s)
 

karlun

Membre

Inscription : 05-05-2010

Messages : 216

Re : Sauter pour revenir, ou continuer...

Salut,

Le tableur est effectivement peu performant.
Mon approche était de le solliciter sur la distribution des signes +ou - de chacune des étapes (N,N-1,N-2,N-...)

La réponse à la question:
"Quel est le minimum de sauts qu'il doit faire, fonction de N entier supérieur à 8,...)"
semble donc bien être 7.

Ce qui m'a intéressé c'est de raisonner au départ de ce thème.

Je pars du principe qu'une séquence dont le nombre de N s’annule >0.

exemple  1  :

+ -

N-(N-1)>0  =>  1>0

La réponse 1 sera l'indice du dernier terme à retrancher de la suite des termes de la séquence pour qu'elle s'annule.

On démarre:
-1
Ensuite:
-2-1
3-2-1    Qui est égale à 0
=> N=3

exemple  2:

++--+-

N+(N-1)-(N-2)-(N-3)+(N-4)-(N-5)>0 => 5>0

La réponse 5 sera l'indice du dernier terme à retrancher de la suite des termes de la séquence.

-5
-6-5
+7-6-5
-8+7-6-5
-9-8+7-6-5
+10-9-8+7-6-5
11+10-9-8+7-6-5 = 0
=> N=11

Évidemment il faut éplucher la séquence pour que jamais l'insecte ne se cogne sur le mur (jamais dans la séquence le résultat ne sera <0)

Ce qui m'intrigue c'est qu'il existe des "équivalences".
Ainsi:

++--+- = +-++--  pour N=11

+-+-++-- = +-++--+-  pour N=14

+-++-+-- = ++-+--+-  pour N=16

++-+-+-- = +++---+-  pour N=18

++-++--- = +++--+--  pour N=20

Je cherche à mettre en évidence la logique qui lie ces égalités.

Auriez-vous une idée pour avancer (un peu plus)?

A+-*/

Dernière modification par karlun (17-08-2012 17:51:18)

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : Sauter pour revenir, ou continuer...

Bonjour,

Je cherche à mettre en évidence la logique qui lie ces égalités.
Auriez-vous une idée pour avancer (un peu plus)?

Si N est le saut de début, le petit programme python du post #7 met en évidence une régularité dont on peut tirer une conjecture pour tout N. Reste ensuite à démontrer cette conjecture (C'est faisable, en trouvant les bons algorithmes....) :

Saut début = 9  : 6  sauts pour revenir à 0
Saut début = 10  : 6  sauts pour être comme après le 1er saut
Saut début = 11  : 6  sauts pour revenir à 0
Saut début = 12  : 6  sauts pour être comme après le 1er saut
Saut début = 13  : 6  sauts pour revenir à 0
Saut début = 14  : 6  sauts pour être comme après le 1er saut
Saut début = 15  : 6  sauts pour revenir à 0
Saut début = 16  : 8  sauts pour revenir à 0
Saut début = 17  : 8  sauts pour être comme après le 1er saut
Saut début = 18  : 8  sauts pour revenir à 0
Saut début = 19  : 8  sauts pour être comme après le 1er saut
Saut début = 20  : 8  sauts pour revenir à 0
Saut début = 21  : 8  sauts pour être comme après le 1er saut
Saut début = 22  : 8  sauts pour revenir à 0
Saut début = 23  : 10  sauts pour revenir à 0
Saut début = 24  : 10  sauts pour être comme après le 1er saut
Saut début = 25  : 10  sauts pour revenir à 0
Saut début = 26  : 10  sauts pour être comme après le 1er saut
Saut début = 27  : 10  sauts pour revenir à 0
Saut début = 28  : 10  sauts pour être comme après le 1er saut
Saut début = 29  : 10  sauts pour revenir à 0
Saut début = 30  : 12  sauts pour revenir à 0
Saut début = 31  : 12  sauts pour être comme après le 1er saut
Saut début = 32  : 12  sauts pour revenir à 0
Saut début = 33  : 12  sauts pour être comme après le 1er saut
Saut début = 34  : 12  sauts pour revenir à 0
Saut début = 35  : 12  sauts pour être comme après le 1er saut
Saut début = 36  : 12  sauts pour revenir à 0
Saut début = 37  : 14  sauts pour revenir à 0
Saut début = 38  : 14  sauts pour être comme après le 1er saut
Saut début = 39  : 14  sauts pour revenir à 0
Saut début = 40  : 14  sauts pour être comme après le 1er saut
Saut début = 41  : 14  sauts pour revenir à 0
Saut début = 42  : 14  sauts pour être comme après le 1er saut
Saut début = 43  : 14  sauts pour revenir à 0
Saut début = 44  : 16  sauts pour revenir à 0

Cordialement

karlun

Membre

Inscription : 05-05-2010

Messages : 216

Re : Sauter pour revenir, ou continuer...

Salut,

j'avais déjà fait tourner le programme que tu nous proposes.
Régularité certes... Reste à tirer une conjecture pour tout N.
J'y pense.
Mais,
Il ne nous dit pas la séquence des + et des - qu'il faut pour atteindre le résultat.
"Sauter pour revenir, ou continuer...", oui mais de quel manière?

Ce sur quoi j'attirais l'attention était d'avoir remarqué que pour un même nombre de sauts, il existe (souvent) deux combinaisons de + et de - différentes.
prenons l'exemple pour N=11:

"++--+- = +-++--  pour N=11"

11+10-9-8+7-6-5=11-10+9+8-7-6-5

"Saut début = 11  : 6  sauts pour revenir à 0"
Oui! mais de deux manières.
++--+-  ou  +-++--

Quoi en penser?

Reste à tirer une conjecture pour tout N !  et ensuite           :-)

Intéressant.
A+-*/

Dernière modification par karlun (19-08-2012 17:30:04)

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : Sauter pour revenir, ou continuer...

Bonjour,

La conjecture est facile à faire : Tour entier N peut être dans une de 7 familles d'entier.
conjecture quelque peu étonnante et inattendue !

Oui, il y a souvent plusieurs chemins et on peut aussi trouver une conjecture sur le nombre de chemins fonction de N dans chaque famille. Il suffit, dans le programme Python proposé, de mémoriser l'antécédent de chaque position avec la position atteinte, ce qui permet de reconstituer, in fine, chacun des chemins possibles (ne pas faire tourner avec N trop grand !)

Pour chacune des 7 familles on peut choisir un algorithme qui recrée un chemin pour des N assez petits, puis "démontrer" que l'algorithme est pertinent pour tout N de la famille!
C'est long, ardu, mais faisable (cela a été fait)....Bon courage ?

Cordialement