Les matheux sont dans la place - pt=prout

[rOut]

Ya sûrement de la suite dans l'air, mais sans doute pas régulière à mon avis. T'es en quelle classe pour avoir une idée ?

J'expliquerai comment j'ai fait plus tard, j'ai pas le temps de rédiger ça pour le moment

[ducon]

C’est un grand classique. Je ne veux pas casser le coup de ton prof de maths, mais la réponse doit se trouver quelque part sur le ternet.

[rOut]

Pour le moment, les démonstrations que je trouve sont toutes un peu tordue, je doute que ce soit ça. Il y a certainement une manière propre de poser le problème...

[Dr.Kant]

Salut,
et bin j'ai galéré. Je suis intéressé pour une solution claire.

Dans le cas où qqn démontre que cette approche est optimale alors je propose une manière de trouver la distance.
N=5000.L=1000.m=1 (nombre de bananes par km)
étape 0.0 : rien
km 0 : N bananes
km 1 : 0 bananes
km 2 : 0 bananes
...
étape 0.1 : éléphant amène n-m bananes au km 1 car il en a mangé m au passage
km 0 : N-L bananes
km 1 : L-m bananes
km 2 : 0 bananes
...
étape 1.0 : éléphant revient au km 0 en prenant m bananes pour la route
km 0 : N-L bananes
km 1 : L-2*m bananes
km 2 : 0 bananes
...
étape 1.1: éléphant revient au km 1 avec n bananes et en mangeant m
km 0 : N-2*L bananes
km 1 : 2*(L-2*m)-m bananes
km 2 : 0 bananes
...
bref ca avance ...
On arrive à l'étape K

étape (K-1).1 : éléphant revient au km 1 avec n bananes et en mangeant m
km 0 : N-K*L bananes
km 1 : (K)*(L-2*m)+m bananes
km 2 : 0 bananes
...

L'éléphqnt conytinue à y aller jusqu'à ce qu'il y ai moins de L bananes au km 0 (donc K=partie entière(N/L)).
Mais maintenant, il y va si il y a assez de bananes pour le retour, si : N-K*L>m.

étape K :
Si : N-K*L>m : l'éléphant revient au km 1 avec n bananes et en mangeant m et en ne laissant aucune bananes
km 0 : 0 bananes
km 1 : N-m*(2*K+1) bananes
km 2 : 0 bananes
Sinon : rien
km 0 : N-K*L bananes
km 1 : (K)*(L-2*m)+m bananes
km 2 : 0 bananes
...

Et là c'est reparti pour un tour entre km 1 et km 2 avec cette fois N = N-m*(2*K+1) ou (K)*(L-2*m)+m suivant le cas
Ya moyen de coder ca facilement !

J'espère que c'est pas trop faux.
Je ne pense pas avoir été clair. Tant pis.

[rOut]

Bon, alors :

Spoiler Alert!

Je vais poser la formule que j'ai trouvé (un peu zarb, mais je vois pas comment la formuler autrement), et faire la démonstration ensuite, par récurrence, comme d'hab pour une suite.

Posons d(n) la distance maxi parcourue par l'éléphant avec n bananes au départ.
Je propose :

* pour n = 1000*k + 1, k >= 1 : d(n) = d(n-1)
* sinon, pour n >= 0 : d(n) = 1 + d(n - 2 * ((n - 1) mod 1000) - 1)

Bon, pour n <= 1000 c'est facile, on a (n - 1) mod 1000 qui vaut 0, donc ça se résume à :
D(n) = 1 + d(n - 1)
Ce qui est trivial : l'éléphant prends toutes les bananes et avance en les mangeant une par une à chaque kilomètre.

A présent, pour n = 1001. On a n = 1000 * 1 + 1.
Le choix optimal est visiblement celui de laisser une banane sur place et de consommer les 1000 autres en avançant, si on avance d'un kilomètre, que l'on revient chercher la banane restante, on se retrouve au point de départ avec 999 bananes (1000 - 1 - 1 + 1 : on pris 1000 bananes, avancé d'1 km, puis reculé d'1 km et pris la banane restante), ça ne vaut pas le coup. On a donc bien
D(1001) = d(1000)

A présent que l'on a montré que la proposition était valable pour n <= 1000 et pour n = 1000 * k + 1 avec k = 1, on va montrer que si c'est vrai pour tout n <= m, m >= 0, alors ça l'est aussi pour n + 1. Et également que si c'est vrai pour tout n <= 1000 * k, k >= 1, ça l'est aussi pour 1000 * k + 1. On aura alors une preuve par récurrence.

Prenons d'abord le cas des 1000 * k + 1 :
Pour conserver un maximum de bananes sur 1km, il est nécessaire de faire des aller retour jusqu'à avoir vidé le tas courant. On prends donc 1000 bananes, on fait 1km, on en pose 998 (il nous en reste 1, car on en a mangé une en chemin), et on revient chercher les autres. Ainsi de suite, on enlève à chaque fois 1000 bananes du tas initial. On se retrouve au bout d'un certain temps avec 1001 bananes sur le tas initial, ce qui revient à la situation de tout à l'heure, ou le choix optimal consiste à prendre les 1000 et à laisser la banane supplémentaire sur place. On a donc la même situation que si l'on avait eu 1000 * k bananes, vu qu'on en laisse une sur place. On a bien d(1000 * k + 1) = d(1000 * k), pour k >= 1.

Pour le cas d(n) = 1 + d(n - 2 * ((n - 1) mod 1000) - 1) :
On suppose que la proposition est vraie pour tout m <= n, n >= 0.
Essayons de calculer d(o = n + 1) (en partant du principe que o n'est pas de la forme 1000 * k + 1). Comme précédemment, pour conserver un maximum de bananes tout en avancant d'1 km, il faut en prendre 1000, avancer d'un km, en laisser 998, et revenir chercher le tas suivant, et ainsi de suite. On peut donc faire (o - 1) mod 1000 aller - retour (2 bananes consommées) avec 1000 bananes jusqu'au kilomètre suivant, avant qu'il ne nous reste un tas <= 1000 bananes. (s'il y en avait 1000, on fait 0 aller retour, 2000, 1 aller retour, etc). On peut donc prendre toutes les bananes restantes et les avancer d'un km (1 banane consommée en plus).
Au final, on a avancé d'un km, et on on a consommé 2 * ((o - 1) mod 1000) bananes pour faire les aller retour, plus une pour le dernier trajet. Au final, il nous reste o - 2 * ((o - 1) mod 1000) - 1 bananes pour la suite. On a donc bien :
D(o) = 1 + d(o - 2 * ((o - 1) mod 1000) - 1)
I.e. :
D(n + 1) = 1 + d(n - 2 * (n mod 1000))
CQFD.

Maintenant, pour calculer la distance précise, il suffit de prendre n = 5000.
D(5000) = 1 + d(5000 - 2 * 4 - 1) = 1 + d(4991)

Or, (n - 1) mod 1000 ne change pas tant que 5000 >= n > 4000 et vaut 4.
Et 5000 - 9 * 111 = 4001.
On a donc d(5000) = 111 + d(4001)

De plus, on a démontré que d(4001) = d(4000)
Or, (n - 1) mod 1000 ne change pas tant que 4000 >= n > 3000, et vaut 3.
Et 4000 - 7 * 142 = 3006
3006 - 7 = 2999
On a donc d(5000) = 111 + 143 + d(2999)

Or, (n - 1) mod 1000 ne change pas tant que 3000 >= n > 2000 et vaut 2.
Et 2999 - 5 * 199 = 2004
2004 - 5 = 1999
On a donc d(5000) = 111 + 143 + 200 + d(1999)

Or, (n - 1) mod 1000 ne change pas tant que 2000 >= n > 1000 et vaut 1.
Et 1999 - 3 * 333 = 1000
On a donc d(5000) = 111 + 143 + 200 + 333 + d(1000)

Ce qui donne au final d(5000) = 111 + 143 + 200 + 333 + 1000 = 1787

Bon, ya pas mal de choses sur lesquelles je ne suis pas certain, notamment pour ce qui est de la meilleure façon d'avancer d'un km, c'est pas une démonstration mathématique. Et également sur la manière dont je calcule le résultat ensuite, c'est fait empiriquement, même si le résultat me semble bon.

Edit : même chose que le Dr.Kant en gros

[Anonyme20240202]

Ouais bon c'est pas très compréhensible ni très rigoureux tout ça :relou:

Je posterai la réponse du prof pour ceux que ça intéresse

[rOut]

S'il trouve moins il a perdu

[Dr.Kant]

Tu pourras demander la preuve de l'optimalité ?
Ca a l'air chaud chaud chocolat. T'es en classe de quoi pauvre fou ?

[AtomicBondage]

Là, clairement, la preuve n'est pas valide s'il n'y a pas de démonstration que c'est la solution optimale. Ça prouve juste que l'on peut parcourir plus de 1000 bananes-km.

[rOut]

Bin, sur un km, le déplacement de 1000 bananes à la fois en revenant chercher le reste est clairement la solution optimale, si tu prends moins de bananes, tu feras plus d'aller-retour, si tu ne les prends pas toutes, tu en auras moins pour la suite.

Tu optimises la quantité de bananes déplacées par rapport à la quantité de bananes mangées.

C'est ce point là qu'il faut démontrer proprement, et j'avoue que je ne sais pas comment m'y prendre, même si ça semble aller de soi.

Parce qu'ensuite, il suffit de dire qu'étant donné que tu sélectionnes la solution optimale à chaque fois que tu avances d'un km, la solution globale est elle aussi optimale : Si tu minimises chaque cout unitaire, alors la somme des couts est minimale elle aussi (enfin c'est sans doute un corollaire du fait que machin truc est continu ou je ne sais quoi, parce qu'un espace tordu doit mettre le bazar dans ce raisonnement, mais on n'est pas dans cette situation).

[Alab]

Sérieux au moins avec son problème de maths je viens d'apprendre que les éléphants aiment les bananes !

Qui a dit que les maths étaient abstraits, voici un exemple des maths au service de problème du quotidien ! (ou pas)

[AtomicBondage]

Parce qu'ensuite, il suffit de dire qu'étant donné que tu sélectionnes la solution optimale à chaque fois que tu avances d'un km, la solution globale est elle aussi optimale

Là, c'est plus douteux comme saut logique.

[rOut]

Là, c'est plus douteux comme saut logique.

Bah non, prenons k1...kn et k'1...k'n tels que kx < k'x pour 1 <= x <= n.
On a donc (k1 + ... + kn) - (k'1 + ... + k'n) = (k1 - k'1) + ... + (kn - k'n) = (?<0) + ... + (?<0), ce qui fait une somme de choses <0 et donc <0.
On a bien (k1 + ... + kn) < (k'1 + ... + k'n)

[Morgoth]

Un éléphants est dans le désert et il a 5000 bananes, il bouffe une banane au kilomètre, mais ne peut en transporter que 1000.

Combien de kilomètres pourra-t-il parcourir au maximum?

Bah, facile, 1000Km. :tropfort:

[rOut]

Pour l'appliquer au problème de l'éléphant, on part du principe que n'importe quelle solution peut être décomposée en une série de déplacements d'un km. Et que du coup la solution globale a un cout égal à la somme des couts pour chaque déplacement d'un km.

Il faut simplement arriver à trouver une mesure du cout sur 1km permettant de définir une solution comme optimale.

[AtomicBondage]

Et si l'on divise encore plus ? La distance minimum entre deux dépôts de banane est de 1 km.

[ducon]

Fonctions composés.

Bon, on reprend depuis le début ?

[DakuTenshi]

Le dernier hors-série de Science Et Avenir parle uniquement de math au fait.

[ducon]

Haaaa, tu m’intéresses. J’espère qu’il n’est pas trop tape à l’œil.

[DakuTenshi]

En fait ça cause surtout de l'intuition des maths, de l'enseignement des maths, des chiffres chelous (pi, 0, 19.5), des probas aussi. Faut que je vois si je peux comprendre la loi de Benford .

[ducon]

La loi de Benford, c’est complètement con. Quand tu prends des nombres dans des listes de nombres (du genre l’annuaire ou les statistiques du nombre de messages de Canard PC), si tu comptes les occurrences de chaque chiffre, eh bien le 1 apparaît le plus, suivi par le 2 et ainsi de suite selon une vague courbe logarithmique.

[DakuTenshi]

Ouais mais je veux comprendre la démonstration moi .

[ducon]

Je doute qu’il y ait une démonstration, puisqu’il est faux pour certaines séries de nombres.

[DakuTenshi]

Ben c'est nullos alors .

[Alab]

Ya un hors série du magazine tangent sur les algorithmes aussi, j'ai acehté et feuilleté (pas trop eu le temps de tout voir en détails) c'est pas mal ça explique aussi l'histoire des maths et introduit un peu sur l'informatique. Sympa quoi.

[Grosnours]

Ben c'est nullos alors .

T'as une ébauche de démonstration dans l'article Wiki.

Mais si tu y réfléchis un peu, ce qui peut sembler peu intuitif au premier abord est assez logique (enfin dans le cas des séries de nombre obéissant a une loi logarithmique ou exponentielle). En effet si tu regardes la représentation graphique d'une fonction exponentielle, tu verras que le nombre de points compris entre deux chiffres de l'axe des ordonnées devient de plus en plus petit. Tous les nombres négatifs ont leur exponentielle inférieure a 1, puis beaucoup moins de nombre ont leur exponentielle inférieure a 2, etc...

Dit de manière plus claire, si tu as une quantité qui augmente exponentiellement (exemple la quantité de RAM dans les PC suit plus ou moins ce schéma) en doublant tous les ans, tu va te retrouver (si on part d'une valeur = 100) avec un an pour doubler cette valeur (donc pendant un tout petit peu moins d'un an le premier chiffre de la valeur sera un), puis après une autre année, le premier chiffre de la valeur est passé par 2, 3 et 4. Puis après une autre année par 5, 6, 7 et 8. Bref, cette valeur aura plus souvent un premier chiffre qui sera 1 (ici pendant quasiment un an) que 8 (pendant quelques jours seulement).

J'espère que j'ai été clair...

[DakuTenshi]

Très clair mais ça m'était déjà venu à l'esprit, moi j'aurais kiffé une démonstration de barbare avec des symboles partout .

[Grosnours]

Elle est pas mal pour cela la mini-démonstration de la wiki.
Groupe topologique, mesure de Haar, c'est des mots magiques !

[ducon]

Ya un hors série du magazine tangent sur les algorithmes aussi, j'ai acehté et feuilleté (pas trop eu le temps de tout voir en détails) c'est pas mal ça explique aussi l'histoire des maths et introduit un peu sur l'informatique. Sympa quoi.

Attends un peu et chope la version complète en librairie.

[Alab]

Attends un peu et chope la version complète en librairie.

Hein ?

Je l'ai acheté déjà, mais que eux tu dire par version complète ?