[Rediffusion d’un article publié en 2011]

C’est pourtant simple !

Le 25 août 2022 - Ecrit par Sylvain Barré Voir les commentaires (75)
Lire l'article en

Tout est si simple quand on a compris. Quand après des heures, des mois, des années
de travail, on finit par voir les objets sous le bon angle.
Amis lecteurs, professionnels des maths ou amateurs, je vous soumets ici un
petit problème qui illustre parfaitement la révélation qui s’opère quand on a enfin compris,
quand on se pose enfin les bonnes questions...

C’est un collègue Russe, Vladimir Vatutin, invité à Vannes, qui me l’a soumis : j’ai adoré !
Le problème est le suivant. Vous avez un verre en main et vous vous trouvez devant
un immeuble de 100 étages. Vous vous demandez alors :

" à partir de quel étage le verre jeté de
la fenêtre se cassera-t-il ?". Voilà une question bien naturelle !

Si vous ne pouvez sacrifier qu’un seul verre, la seule stratégie
est de tester les étages un par un, en remontant. Votre ami qui lui aussi a un verre
en main vous propose son verre pour accélérer l’expérience. Le jeu consiste alors
à trouver une stratégie qui donne le nombre minimal de lancers,
pour répondre à la question de façon certaine (en cassant au plus 2 verres) dans tous les cas. Effectivement, on peut gagner
beaucoup d’essais grâce au second verre. Par exemple, on peut jeter un verre du cinquantième
étage et n’avoir alors plus qu’au plus 50 étages à tester. Cela donne alors une solution en moins de
51 lancers (la pire des situations étant celle où le verre ne casse même pas du 100 ème étage). Mais il y a bien mieux ! Lancer le premier verre au 10 ème, puis au 20 ème s’il ne se casse pas, et ainsi de suite de 10 en 10. Puis dès qu’il se casse, on utilise le second pour affiner la fourchette dans l’intervalle déterminé en testant au plus 9 étages intermédiaires. Cela fait
au plus 19 lancers !
On a l’impression que les stratégies vont dépendre de l’arithmétique de ce nombre d’étages.
Pour garder le suspens, je ne donnerai la solution à ce problème que dans 2 jours. Je dis seulement
qu’on peut faire mieux que
19. Mais d’ici là,
si vous avez d’autres petits problèmes de ce genre, qui semblent, d’un prime abord d’une
assez grande complexité, mais qui, après coup sont très accessibles n’hésitez
pas à commenter ce billet pour les faire partager au plus grand nombre.

Commentaire sur l'article

C’est pourtant simple !

le 7 octobre 2011 à 10:05, par Bruno Duchesne

Il y a aussi le problème des ponts de Könisberg dont la solution donnée par Euler est finalement simple une fois connue !

En plus, il n’y a même pas de verre à casser ; )
Répondre à ce message

C’est pourtant simple !

le 17 janvier 2012 à 01:06, par Marie-Anne

Très bel exemple pris ici :D !
Marie-Anne, du site de poêle à granulé.
Répondre à ce message

C’est pourtant simple !

le 7 octobre 2011 à 10:27, par Sylvain Barré

Oui bel exemple ! Mais on ne casse pas plus de verre devant l’immeuble qu’on ne fait de grande promenade dans Königsberg :-)
Répondre à ce message
C’est pourtant simple !

le 7 octobre 2011 à 12:47, par Olivier

J’ai une solution en au plus 14 lancers. Peut-on faire mieux, ou est-ce l’optimal ?
Répondre à ce message

C’est pourtant simple !

le 7 octobre 2011 à 13:00, par Sylvain Barré

Trop fort ! Essayez donc avec 105 étages maintenant...
Répondre à ce message

C’est pourtant simple !

le 7 octobre 2011 à 14:20, par Olivier

J’ai encore la même solution qui fonctionne, et toujours en au plus 14 lancers. Et on ne peut pas aller plus loin en 14 lancers au maximum : tout immeuble à plus de 106 étages nécessite dans le pire cas au moins 15 lancers. On peut ensuite aller jusqu’à 120 étages (inclus) avec 15 lancers, puis 136 (inclus encore) avec 16 lancers.
Est-ce bien cela ?
Répondre à ce message

C’est pourtant simple !

le 7 octobre 2011 à 14:43, par Sylvain Barré

Il me semble que vous avez compris, il faut chercher la preuve maintenant... et tout deviendra limpide !
Répondre à ce message

C’est pourtant simple !

le 7 octobre 2011 à 12:51, par électron

Pas mieux ...
Répondre à ce message
C’est pourtant simple !

le 7 octobre 2011 à 14:06, par Jonas Kahn

Très joli en effet !
Une bonne base pour des sujets type Math en Jeans.

Pour ceux qui ont déjà bien avancé : tester un immeuble de 129 étages en neuf lancers avec trois verres.

Sinon, dans les problèmes à prendre par le bon bout, un de mes préférés est celui de la mouche entre les deux trains, mais il n’y a pas grand-chose à creuser après...
Répondre à ce message

C’est pourtant simple !

le 7 octobre 2011 à 14:53, par Sylvain Barré

Tu nous appâtes avec ta mouche... il faut nous en dire plus ! Oui, ce genre de problème est bien dans l’esprit de Math en Jeans.
Répondre à ce message

C’est pourtant simple !

le 7 octobre 2011 à 15:13, par Jonas Kahn

C’est un archi-classique :

Deux trains partent à la même heure. L’un va de Strasbourg à Mulhouse (110 km) à 50 km/h (c’est une relique de musée). L’autre fait le trajet inverse, à 60 km/h (une relique plus moderne).
Une mouche de compétition part de Strasbourg au même moment. Elle vole à 200 km/h, et suit la voie. Au bout d’un moment, elle va croiser l’autre train : elle fait alors demi-tour pour ne pas le toucher. Quand elle touche le premier train, elle refait demi-tour. Et ainsi de suite, elle rebondit de train en train une infinité de fois, jusqu’à ne plus pouvoir le faire parce que les deux trains se croisent.
Quelle distance aura-t-elle parcouru au total entre ces deux trains ?

Quand on a posé la question à Von Neumann, il a répondu instantanément. On lui demande s’il a vu l’astuce. « Quelle astuce ? J’ai sommé la série ! »
Répondre à ce message

C’est pourtant simple !

le 7 octobre 2011 à 15:25, par Sylvain Barré

Très beau effectivement ! Et l’anecdote sur Von Neumann est savoureuse. Pour revenir aux verres, j’ai vu des mathématiciens professionnels y passer du temps pour finir par donner leur langue au chat.
Répondre à ce message

C’est pourtant simple !

le 7 octobre 2011 à 15:16, par Christine Huyghe

L’énoncé du problème de la mouche est sans doute celui-ci :
Devoir de vacances

Une question : est-ce que c’est parce que l’auteur de ce billet est un spécialiste des immeubles [1] qu’il prend plaisir à résoudre des énigmes faisant intervenir des immeubles ?

[1] Un objet mathématique introduit par J. Tits ...

Répondre à ce message

C’est pourtant simple !

le 7 octobre 2011 à 15:36, par Sylvain Barré

Oui, la mouche avait déjà volé sur le site cet été...
Vladimir m’avait dit : « tiens, tu t’intéresses aux immeubles, j’ai un problème pour toi ! »
Répondre à ce message
C’est pourtant simple !

le 8 octobre 2011 à 13:55, par Jonas Kahn

Oui, c’était bien cette mouche (que vous préférez faire voler entre Paris et Marseille).

Tiens, un autre qui a une solution très simple :
Dans un avion, chaque passager a sa place numérotée. Mais le premier des passagers de cet avion rempli décide de s’asseoir (uniformément) au hasard dans l’appareil plutôt que de s’asseoir forcément à sa place.
Les passagers suivants entrent un à un. Ils prennent leur place si elle est libre, sinon s’assoient au hasard.
Quelle est la probabilité pour que la dernière personne à entrer s’assoie à sa place ?
Répondre à ce message

C’est pourtant simple !

le 8 octobre 2011 à 15:25, par Sylvain Barré

Génial ton problème ! Ca me fait penser à la patate chaude, vraiment pile dans l’esprit des problèmes auxquels je pensais : merci !
Répondre à ce message
C’est pourtant simple !

le 8 octobre 2011 à 15:35, par Sylvain Barré

Si dans l’énoncé, on remplace « rempli » par « bourré », on retombe sur une histoire de verres :-)
Répondre à ce message

C’est pourtant simple !

le 9 octobre 2011 à 14:55, par Jonas Kahn

Oui, mais alors ce n’est plus une version pour mineurs !
Répondre à ce message

C’est pourtant simple !

le 9 octobre 2011 à 16:37, par Sylvain Barré

Oui, tu as raison, restons dans les clous :-)
Répondre à ce message

SOLUTION du problème de l’AVION

le 10 octobre 2011 à 23:36, par Jonas Kahn

S’il y en a qui ont cherché :

la dernière personne a toujours une chance sur deux de s’asseoir à sa place, quelle que soit la taille de l’avion (s’il a au moins deux places) !

Pourquoi ?
Imaginons qu’un passager quelconque s’assied à la place du dernier : le dernier passager ne pourra alors pas s’asseoir à sa place.

Imaginons maintenant que le passager quelconque s’assied à la place du premier passager, plutôt. Mais dans ce cas, après qu’il s’est assis, les sièges occupés sont exactement ceux des passagers déjà assis ((*) preuve ci-dessous). Donc tous les passagers suivants trouvent leur propre siège.

Du coup la seule question est de savoir quel siège sera occupé en premier : celui du premier, ou celui du dernier passager ? Ce sera forcément par un passager qui s’assied uniformément au hasard (parce que sa place est occupée, ou parce que c’est le premier), il a donc autant de chances d’occuper un siège que l’autre : 1/2.

(*) Après l’entrée de chaque passager, ce qui compte, c’est la différence entre les sièges vides et les sièges des passagers qui doivent encore entrer.

Si le premier passager ne s’assied pas à sa place, un siège qui devrait être vide est occupé, et le siège du premier passager est vide.

Quand un nouveau passager entre, s’il s’assied à sa place, pas de changement.
Sinon, c’est que c’est son siège qui était « injustement » occupé. Donc, il n’est plus injustement occupé. Maintenant, soit le passager s’assied sur le siège du premier passager, et les sièges vides sont les bons sièges vides, soit il s’assied sur un autre siège, qui devient à son tour injustement occupé. On reste toujours avec un seul siège injustement occupé, et celui du premier passager vide.
Répondre à ce message

SOLUTION du problème de l’AVION

le 11 octobre 2011 à 09:56, par Sylvain Barré

Par récurrence sur le nombre de sièges, c’est peut-être plus facile à raconter...
Répondre à ce message

C’est pourtant simple !

le 7 octobre 2011 à 22:38, par florian

Un ami professeur particulier à domicile en mathématique a récemment été collé par un exercice de maths niveau terminale.

Voici l’énoncé du problème « Voisins de table - voisins rentables » :

Dix personnes sont autour d’une table. Dix jetons portant les numéros de 1 à 10 sont distribués au hasard à ces 10 personnes. Chaque joueur gagne une somme égale (en €) au total des nombres inscrits sur son jeton ainsi que sur ceux de ses voisins de gauche et de droite.
Ainsi peut-on affirmer : « Au moins une des dix personnes aura un gain au moins égal à M€ ».
Quel est le plus grand nombre que l’on peut mettre à la place de M ?

L’énoncé est un peu alambiqué : il s’agit en fait de trouver un minorant des gains maximaux présents dans chaque distribution de jetons.

Après s’être creusé la tête avec quelques confrères, nous avons abouti à une solution pas si simple que je publierai ici sous peu : http://goutte-de-science.net/blog/enigme-voisins-de-table-voisins-rentables/. En attendant, vous pouvez déjà utiliser les indices pour vous creuser les méninges !

Si vous avez une solution simple, comme cela semble être le cas pour le problème posé dans cet article, je suis preneur ! La simplicité se cache encore sûrement dans le bon angle de vue...

En attendant vos éventuels commentaires et/ou solution sur l’énigme « voisins de table - voisins rentables » je continue à tourner autour de l’immeuble, à la recherche du bon point de vue, tout en évitant les verres qui tombent... Si l’un de ceux que vous lancez ne se brise pas, n’en déduisez pas trop rapidement que c’est le bon étage, il se pourrait bien qu’il ait été amorti par mon crâne !
Répondre à ce message

C’est pourtant simple !

le 8 octobre 2011 à 13:56, par Jonas Kahn

J’arrive à la solution (et après consultation de vos indices, par une méthode similaire), mais je n’irais certainement pas qualifier la méthode de non-alambiquée...
Répondre à ce message

C’est pourtant simple !

le 8 octobre 2011 à 15:04, par Sylvain Barré

Oui, petit alambique qui demande de prendre un crayon :-) Mais le problème reste de solution élémentaire pas trop longue, juste un peu alambiquée !
Répondre à ce message

C’est pourtant simple !

le 9 octobre 2011 à 10:37, par florian

Félicitations pour être arrivés si rapidement à une solution !

Mais toujours pas de solutions non-alambiquées en perspective ?
Répondre à ce message

C’est pourtant simple !

le 9 octobre 2011 à 09:35, par Sylvain Barré

Les alambics proviennent parfois du fait des effets de bord. Pour des valeurs plus grandes que N=10, la solution se simplifie sûrement !
Répondre à ce message

C’est pourtant simple !

le 9 octobre 2011 à 10:38, par florian

Bonne remarque, ça vaudrait le coup de tester pour N>10 effectivement, voire envisager une généralisation à N quelconque !
Répondre à ce message

Voisins rentables pour N quelconque

le 11 octobre 2011 à 16:23, par Rémi Peyre

Bonjour,

J’y ai passé pas mal de temps, mais je pense avoir enfin résolu le problème des voisins rentables pour N quelconque ! J’écrirai la réponse sous la forme M(N) = 3(N+1)/2 + m(N), de sorte que m(N) = 0 correspondrait au cas où tous les gens reçoivent la même somme.

On trouve en général
m(N) = 3/2 pour N pair, et
m(N) = 2 pour N impair,
avec la liste finie d’exceptions suivante :
m(1) = 0
m(2) = 1/2
m(3) = 0
m(5) = 1
m(6) = 1/2
m(9) = 1
m(15) = 1

Je n’ai pas rédigé de preuve pour l’instant, mais je peux donner des éléments à ceux qui me demanderont par e-mail (vous trouverez facilement mon adresse sur le web).
Répondre à ce message

C’est pourtant simple !

le 9 octobre 2011 à 14:59, par Jonas Kahn

J’en doute.
Il y a un argument simple qui montre que pour N pair supérieur à 7, M est au moins égal à (3N+6)/2. On peut donc l’utiliser aussi pour le 10, sans passer par prouver que 17 ne marche pas.
Par contre je ne vois pas comment systématiquement construire une solution pour cette valeur, je ne suis même pas complètement certain que ce soit la bonne.

Pour N impair, le même genre d’idées donne la borne (3N+5)/2, et on a encore moins de marge de manœuvre.
Répondre à ce message

C’est pourtant simple !

le 9 octobre 2011 à 19:16, par florian

Je suis curieux Jonas, quel est cet argument simple qui m’a échappé ?
Répondre à ce message

C’est pourtant simple !

le 9 octobre 2011 à 21:00, par Jonas Kahn

En fait, c’est ce que vous faites dans votre solution, pas à pas.

Je vais reprendre vos notations : $N_i$ est le numéro du joueur $i$, $g_i$ son gain.
Donc $g_i = N_i + N_{i+1} + N_{i+2}$.
Je travaillerai toujours modulo $n$ le nombre d’invités.

Première remarque : deux joueurs consécutifs ont des gains différents, la différence valant $N_{i+3} - N_i$.

Première conséquence : le nombre de joueurs gagnant $M$ est au maximum $n/2$.

Deuxième conséquence, la somme des gains, qui est forcément $3(n+1)n/2$, est majorée par $(n/2)(2M - 1)$, ce qui n’arrive que si $(n/2)$ joueurs gagnent $M$, et $(n/2)$ gagnent $(M-1)$.

Si $M = (3n+4)/2$, l’inégalité est saturée.

Revenons à la première remarque : si $g_i=M$, alors $g_{i+2k+1} = M-1$ et $g_{i+2k} =M$ pour tout $k$.
Notamment $N_{i+3} = N_i -1$ et $N_{i+6} = N_{i+3} +1 = N_i$, ce qui est impossible si $n>6$.

[Écrit comme cela, cela semble très lourd et technique, mais je déteste cette formulation en équations, ce n’est pas comme ça que je pense, et je viens seulement de l’écrire, mais c’est plus facile à écrire formellement que dire que les $g_i = M$ nous font « gagner » un demi euro, les autres nous font « perdre » au moins un demi euro, et sont au moins la moitié...)
Répondre à ce message

C’est pourtant simple !

le 12 octobre 2011 à 14:14, par florian

Merci beaucoup pour vos éléments de démonstration. Je vous ai répondu sur mon blog, puisque nous allons petit à petit nous éloigner du sujet inital :)
Répondre à ce message

C’est pourtant simple !

le 9 octobre 2011 à 19:14, par florian

Je viens de publier un exemple de solution ici http://goutte-de-science.net/blog/e....

Les commentaires sont les bienvenus :)
Répondre à ce message

C’est pourtant simple !

le 8 octobre 2011 à 11:38, par Menura

Ça serait-y pas une méthode qui coupe les étages en quatre, i.e. en deux après les avoir coupés en deux, et ainsi de suite à la va que je te jette le godet ? Donc en 6, 7 lancers max si on a pas de pot ou de bol, la coupe est sifflée ! Encore une histoire à Neper-dre rien mais à gagner une boutanche de champ, si je parie. Et je parie !
Répondre à ce message

C’est pourtant simple !

le 8 octobre 2011 à 15:11, par Raphaël

Si l’on disposait de suffisamment de verres, oui cela marcherait, sauf qu’on ne dispose que de deux verres ! Et puis il faut imaginer les pires scénarios possibles !

Étage critique : étage solution du problème.

On voit se profiler deux principes, si je ne me trompe pas :

Principe I : la fonction qui au numéro d’ordre du test (optimal) du premier (respectivement du second) verre associe l’étage est strictement croissante.

En effet, pour fixer les idées, on prend le premier verre, et les deux premiers tests s’effectuent aux étages n et (n+1). Si l’on inverse l’ordre, il y a un risque que le verre casse à l’étage (n+1) avant qu’on n’ait pu tester l’étage n (et donc que l’intervalle des étages auquel appartient l’étage critique soit plus grand). Et donc potentiellement, il y a un risque que l’on teste le second verre un nombre de fois plus grand d’une unité.

Principe II : sous l’hypothèse du principe I, quelle que soit la manière choisie d’utiliser le premier verre le second devra être lancé entre l’avant-dernier (pas de casse) et le dernier essai (où le premier verre vient de se briser).

Pas de choix ici non plus, dans la pire situation, on risque d’être dans l’incertitude, du genre l’étage critique pour nos verres est entre les 10e et 12e (ou plus) étages, par exemple.

J’ai donné ce problème à des élèves de seconde, avec des pastèques exceptionnelles résistantes en supposant que la structure reste la même si elles ne se brisent pas !
Répondre à ce message

C’est pourtant simple !

le 8 octobre 2011 à 15:32, par Sylvain Barré

Et vous élèves, ils en pensent quoi ?
Répondre à ce message

C’est pourtant simple !

le 8 octobre 2011 à 19:48, par Raphaël

Ils avaient vite fait de tester d’abord la méthode par dichotomie, puis un peu plus tardivement la méthode ’un premier verre pour les dizaines, puis le second pour les unités’. La méthode optimale n’est pas sortie dans l’heure, je leur ai dit qu’il existait une meilleure solution que les 19 essais.
Répondre à ce message

C’est pourtant simple !

le 8 octobre 2011 à 17:25, par Menura

En fait je trouve que ce problème est typique d’un problème de maths posé par un matheux. N’importe quel enfant de - de six ans (allez me chercher un enfant de - de 6 ans…) pourrait répondre à la question dans la seconde (et donc en bien moins de deux jours) en faisant l’économie de deux verres dans le service de sa mère. Le premier étage suffit pour pèter le verre, et même simplement le laisser tomber de la main devrait permettre d’arriver à la réponse à moins que le verre soit en verre incassable et c’est pas dit dans l’énoncé.
Répondre à ce message

C’est pourtant simple !

le 9 octobre 2011 à 09:28, par Sylvain Barré

N’est-il pas le propre du mathématicien que de voir autour de lui mille prétextes à exciter sa curiosité, à stimuler son imagination ? Je voulais montrer ici que l’essentiel est de garder l’esprit ouvert, prêt à découvrir « la » bonne vision des choses. Et quand on l’a trouvée, on est tellement content qu’on tente de faire partager son plaisir avec son entourage... et ça, ce n’est pas facile !
Répondre à ce message

C’est pourtant simple !

le 9 octobre 2011 à 11:44, par florian

Rha, je sèche ! C’est agaçant :)

J’ai testé toutes les divisions euclidiennes de 100, j’obtiens quelques possibilités en 18 lancers au mieux.

Comme vous semblez l’indiquer dans l’énoncé, le bon angle d’attaque ne doit pas être purement arithmétique...
Répondre à ce message

C’est pourtant simple !

le 9 octobre 2011 à 16:41, par Sylvain Barré

Il faut lancer un verre et se poser la bonne question...
Répondre à ce message

C’est pourtant simple !

le 9 octobre 2011 à 19:35, par Menura

J’ai trouvé une solution en 10 lancers avec 1 seul verre ou en 15 lancers avec deux verres et le deuxième verre reste peut être pas cassé. Ça serait-y bon ? En fait, pour être complet, il y a un cas où on n’a pas la réponse c’est si l’immeuble est pas assez haut et que le verre ne se casse pas du 100e étage. Dans ce cas, on peut essayer de trouver un immeuble à 120 étages et d’obtenir la réponse toujours en 15 lancers. Mais il se peut que le verre (le premier) ne casse toujours pas du 120e étage. Dans ce cas, il faut aller à Dubai pour trouver un immeuble encore plus haut mais cette fois, la solution sera peut-être obtenue si le verre se décide à se casser mais cette fois en plus de 15 lancers. Je vais essayer d’établir la formule théorique mais c’est pas gagné quoique c’est probablement celle du petit C. F Gauss qui avait - de 6 ans quand il l’a trouvé. Je savais bien qu’il me fallait un gamin pour obtenir rapidement la réponse !
Répondre à ce message
C’est pourtant simple !

le 9 octobre 2011 à 20:19, par Menura

Voilà la formule annoncée pour trouver le nombre n minimal de lancers pour un immeuble de N étages. C’est : n = plafond(-1/2 + racine carrée(1/4 + 2N)), la fonction plafond donnant l’entier naturel immédiatement supérieur. Dans notre cas : n = plafond(-1/2 + racine carrée(1/4 + 2x100)) = plafond(14,65) = 15. Remarque pour N= 120, n= pilepoil(15), la fonction pilepoil étant la fonction où la fonction plancher et la fonction plafond donnent le même résultat mais là je ne suis plus très rigoureux alors je m’arrête là.
Répondre à ce message
C’est pourtant simple !

le 10 octobre 2011 à 00:00, par Menura

Bon j’améliore : j’ai trouvé la solution en 12 lancers avec un seul verre qui casse au 100e étage ou en 14 lancers avec deux verres (et dont le premier a forcément cassé et toujours le deuxième verre qui peut rester intact au 14ème lancer. Je m’étais planté dans mes calculs difficiles : des sommes d’entiers naturels à moins de deux ou trois chiffres !
On remplace cette fois la limite de la méthode par N=105 étages = 14x15/2 et on peut toujours obtenir la réponse en 14 lancers minimum que ce soit avec un ou deux verres à condition qu’un des deux casse. La formule est la même mais avec la fonction plancher cette fois. Et on obtient n = pilepoil(14) pour N=105.
Sacré gamin ce sylvain : il m’aura tourné en bourrique. Bon j’attaque le pb à 3 verres.
Répondre à ce message
C’est pourtant simple ! SOLUTION

le 10 octobre 2011 à 10:45, par Sylvain Barré

J’avais promis une solution deux jours plus tard, je me contenterai de signaler un lemme :

Toute stratégie qui commence par un lancer au niveau k donne une solution en plus de k coups (le verre peut casser au premier coup).

Et donc, pour qu’une stratégie en k coups commence par un lancer au niveau k, il faudra lancer la seconde fois (si le verre ne casse pas) plus bas que le niveau k + (k-1), et la troisième fois (s’il ne casse toujours pas) : k + (k-1) + (k-2). Vous voyez ?

1+2+...+14 = 14*15/2 = 105

Une fois compris le problème pour 2 verres, on s’attaque à trois verres de la même façon. C’est moins facile à faire de tête cette fois quand même :-) On atteint alors, comme l’a déjà dit Jonas, 129 étages maximun en moins de 9 lancers.
Répondre à ce message

C’est pourtant simple ! SOLUTION

le 10 octobre 2011 à 15:31, par Menura

C’est 129 étages max avec 3 verres en moins de 9 lancers ou bien plutôt 129 étages max avec 3 verres et au plus 9 lancers ?
Est-ce que c’est aussi 133 étages max avec 4 verres et au plus 7 lancers ?
Moi ce que j’aimerais c’est une jolie formule qui permette de trouver le nombre L de lancers minimal connaissant le nombre E d’étages et le nombre V de verres. Puisque le propre du mathématicien est de généraliser, ça devrait pas vous poser de problème à vous (parce que à moi si, hélas !).
En tout cas, je remarque que je n’ai pas la chance qu’on me lise comme le bon élève premier de la classe Jonas qui a trouvé tout de suite, lui. Ma petite formule, elle a pas l’air de vous intéresser du tout. Je suis triste, j’avais pourtant essayé de faire l’effort de m’ouvrir l’esprit en me creusant les méninges comme vous me l’aviez hautement et délicieusement recommandé.
Doit-on en tirer la moralité : l’internet, c’est comme l’école, en résumé, réservé aux meilleurs, les autres, taisez-vous et démerdez-vous ? Mais il est vrai que « partager son plaisir avec son entourage... ça, ce n’est pas facile ! »
Répondre à ce message

Solution

le 10 octobre 2011 à 18:07, par Rémi Peyre

Allons, Menura, ne soyez pas vexé... Déjà, Jonas Kahn est un mathématicien professionnel ; sa performance est donc à relativiser (sans rancune, Jonas ?) :-)

Concernant votre formule (qui est juste, bien que votre première application numérique soit incorrecte puisqu’on doit trouver 14 et non pas 15), elle est en effet un complément de réponse appréciable au problème, et c’est tout à votre honneur que de l’avoir écrite. Encore que, dans un sens, l’astuce était justement de poser la question à l’envers, en se demandant non « combien de lancers nécessaires pour un immeuble de telle hauteur ? », mais plutôt « jusqu’à quel hauteur peut-on trancher avec un tel nombre de lancers ? »...

Il faut aussi prendre en compte que le but de cette note n’était pas vraiment de lancer un concours dont les gagnants seraient félicités en commentaires. La note n’invitait d’ailleurs pas les lecteurs à poster leurs solutions, mais uniquement à proposer d’autres problèmes. Sylvain Barré a gentiment répondu à un grand nombre de commentaires postés ; je pense qu’il vaut mieux l’en remercier que le blâmer de n’avoir pas répondu à tous.

À l’avenir, je vous suggère, pour maximiser votre probabilité d’avoir une réponse, de ne poster de message qu’après avoir étudié le problème bien à fond : il est en effet plus agréable et plus facile de répondre à un seul post bien ficelé qu’à une foultitude de petits commentaires qui sont encore en cours de réflexion (même si c’est très intéressant aussi de connaître le chemin de votre réflexion !).

Bien cordialement.
Répondre à ce message
C’est pourtant simple ! SOLUTION

le 10 octobre 2011 à 23:07, par Jonas Kahn

En fait, c’est très difficile de donner une solution lisible générale en fonction de L, E et V. Vous voyez bien à quoi ressemble votre formule pour $V=2$, c’est déjà bien plus compliqué que s’il n’y a qu’un verre !

Comme dit Rémi (sans rancune, non), le problème inverse est plus simple, le nombre d’étages $E$ en fonction de $V$ et $L$. L’écriture de la solution est aussi plus simple.

Et encore, il est simple d’écrire une formule de récurrence, mais une formule fermée sans utiliser $V$ sommes imbriquées, je ne vois pas comment faire...
Répondre à ce message

C’est pourtant simple ! SOLUTION

le 11 octobre 2011 à 00:08, par Menura

Merci pour cette intervention, monsieur que j’ai nommé un peu méchamment il est vrai le premier de la classe (mais qui semble bien l’être après un coup de Google). Votre réponse est sur un mode un peu moins paternaliste que celle du père Peyre ( (- :, c’est bien comme ça qu’on fait pour détendre l’atmosphère, n’est-ce pas ?).
Ma formule est vachement compliquée : c’est la solution d’une équation du second degré !!!
J’ai des bouquins de maths plein de formules avec plein de sommes et d’intégrales imbriquées et qui parfois, magie, magie, se simplifient alors votre argument me parait rigolo.
C’est surement parce que que je n’ai pas votre flair. Il parait que les forts en maths ont un cerveau bâti à l’origine pas comme le pékin ordinaire que je suis.
J’avais cru comprendre que ce site se voulait être une ouverture des maths au grand public. Il semblerait que ce ne soit juste le moyen de faire ronron entre matheux qui se connaissent à coups de petits pbs de connivence comme chez les journalistes et les capitalistes (ouh la la voilà que je mélange tout)
Excusez-moi de vous avoir déranger car je croyais que le but du jeu au départ c’était de trouver une solution avec le minimum de lancers et je m’aperçois que en fait, il s’agit de trouver le nombre d’étages parce que c’est plus simple.
Je n’ai décidément rien compris et je vous ai fait perdre et gâcher votre temps de roucoulement entre vous. Je suis désolé.
Bonne soirée.
Répondre à ce message

C’est pourtant simple ! SOLUTION

le 11 octobre 2011 à 10:14, par Sylvain Barré

On cherche bien une solution avec un nombre minimal de lancers. On trouve que ce nombre minimal est constant sur un intervalle entre deux nombres triangulaires : par exemple 14 lancers entre 92 et 105 étages. On peut alors poser le problème d’une autre façon, à nombre de lancers constants, trouver l’immeuble le plus haut. Au passage, pour ce maximum, il n’y a qu’une seule solution, sinon, plusieurs...
Répondre à ce message
C’est pourtant simple ! SOLUTION

le 12 octobre 2011 à 16:53, par Martin Anderegg

En fait il semblerait que Menura ait eu la bonne intuition et qu’une formule explicite existe pour la hauteur maximale. Notons $H(V,L)$ la hauteur maximale qu’un immeuble peut avoir pour être « testé » à l’aide de $V$ verres et $L$ lancers. Comme le fait remarquer Jonas, il est relativement aisé de se convaincre, par des arguments similaires au cas $V=2$, que $H(V,L)$ satisfait la formule de récurrence
\[H(V,L)=\sum_{i=0}^{L-1}(H(V-1,i)+1).\]
Si on se donne la peine de calculer pour $V=3$ on voit une formule générale se dessiner, formule qu’on peut ensuite prouver par récurrence :
\[H(V,L)=\sum_{i=1}^V{L \choose i}\]
Répondre à ce message

C’est pourtant simple ! SOLUTION

le 12 octobre 2011 à 19:23, par Sylvain Barré

Reste plus qu’à comprendre cette formule pour peut-être avoir enfin vraiment compris le problème !
Répondre à ce message
C’est pourtant simple ! SOLUTION

le 13 octobre 2011 à 14:38, par Jonas Kahn

Ah oui très bien ! Je vais manger trois triangles de Pascal pour ce soir !

On voit bien tout ce qui peut servir directement sur la formule, ou presque : polynôme de degré $V$, dont le coefficient du premier terme est $\frac{1}{V!}$ (bon, ça on l’avait facilement directement par la formule de récurrence),
ou le fait que pour $L \leq V$, on a $H = 2^L - 1$, par exemple.
Répondre à ce message

C’est pourtant simple ! SOLUTION

le 14 octobre 2011 à 09:14, par Sylvain Barré

Je voulais dire qu’on a l’impression que cette somme fait référence à une partition en fonction du nombre de verres cassés, puis on cherche où ils ont pu casser...
Répondre à ce message

C’est pourtant simple !

le 10 octobre 2011 à 11:40, par amic

Dans le même genre de problème, et ça ressemble un peu à l’histoire de la mouche, il y a 100 fourmis sur un rebord de table de 1m. Elles avancent toutes à une vitesse de 1m par minute, et quand elles se rencontrent elles font chacune demi-tour. Si elles arrivent au bord de la table elles tombent.

Vont-elles toutes tomber au bout d’un moment ? En combien de temps ?
Répondre à ce message

C’est pourtant simple !

le 10 octobre 2011 à 22:53, par Jonas Kahn

Oui, encore une très belle énigme !
Avec une astuce qui est « réellement » utilisée dans l’étude de systèmes de particule dans certains modèles.
Répondre à ce message

C’est pourtant simple !

le 10 octobre 2011 à 18:03, par Denis

Merci pour cette belle enigme, surprenante et jolie !

J’ajoute aussi une enigme alors, que je trouve tout aussi agréable à comprendre :

Comment accrocher un tableau (on peut modéliser par juste une boucle de ficelle) en utilisant 2 clous tels que si on retire n’importe quel clou le tableau tombe ?

ps : quelle surprise de te trouver là Amic ;)
Répondre à ce message

C’est pourtant simple !

le 10 octobre 2011 à 23:01, par Jonas Kahn

J’ai eu l’occasion de voir Pierre Duchet donner ce problème à un groupe de lycéens, en leur donnant des porte-manteaux, des cordes, et en les divisant en deux. À mi-distance, chaque groupe racontait les idées qu’il avait eues à l’autre.

Cela reste peut-être le plus beau moment de vulgarisation mathématique que j’aie vu à ce jour. Les lycéens ont cherché, eu des idées diverses, n’ont pas trouvé de solutions complètes, mais certaines de leurs idées a inspiré à Pierre Duchet un sujet de thèse potentiel...

Puis, contrairement aux problèmes un peu fermés cités jusqu’ici, il y a plein de solutions profondément différentes (je n’en connais qu’une, celle basée sur les nœuds croissants).
Répondre à ce message

C’est pourtant simple !

le 11 octobre 2011 à 03:08, par Denis

Effectivement c’est excellent pour la vulgarisation, d’ailleurs on me l’a raconté en tant que future animation pour la fête de la science.

Par contre l’approche des « noeuds croissants » ne me dit rien. Est-ce que cela fait référence à la généralisation du problème avec n clous (qui a aussi une solution !) ?
La solution que je connais se formalise plutôt avec la notion de groupe...
Répondre à ce message

C’est pourtant simple : expérimentation.

le 11 octobre 2011 à 09:33, par ROUX

Sous l’hypothèse d’un verre mathématique qui casse toujours en exactement « m » morceaux assez petits pour avoir, à 5% près, la même masse et la même surface de contact au sol, on procède à deux lâchers des étages les plus hauts afin de garantir la rupture et on analyse la distance (unique pour chaque hauteur, ce sont des fragments mathématiques) à laquelle les fragments se trouvent. L’énergie potentielle et donc, dans le cas où l’air mathématique ne frotte pas, l’énergie disponible pour casser le verre est une fonction affine de la hauteur. La distance parcourue par les fragments à partir du point d’impact est elle aussi affine puisqu’il s’agit du travail de la force de frottement (indépendante de la vitesse) sur le sol.
Si on trace deux points ayant pour ordonnées la distance à laquelle se trouvent les fragments et en abscisse la hauteur du lâcher, on a une fonction affine dont l’intersection avec l’axe des abscisses a pour abscisse la hauteur de lâcher à laquelle le verre se casse sans dispersion des fragments.

Deux(2) lâchers suffisent donc.

Dans le cas de verres et d’air réels, la prise en compte de la théorie statistique de la fragmentation (1942-1947) de Sir Nevill MOTT et la prise en compte des frottements peut augmenter légèrement le nombre de lâchers afin de déterminer éventuellement plus de deux paramètres mais il restera sans aucun doute très largement inférieur à 14.

Par ailleurs, ce nombre de lâchers restera indépendant de la hauteur de la tour tant que la vitesse limite des fragments, due aux frottements, n’est pas atteinte.

Conclusion : nombre de lâchers assez voisin de deux(2) et assez indépendant de la hauteur de la tour.
Répondre à ce message

C’est pourtant simple : expérimentation.

le 12 octobre 2011 à 14:13, par florian

Oh que j’aime cette solution de physicien :)
Répondre à ce message
C’est pourtant simple : expérimentation.

le 13 octobre 2011 à 14:33, par Jonas Kahn

J’aime beaucoup le principe !

Maintenant, l’hupothèse de se caser toujours en le même nombre de morceaux (et donc même énergie de rupture) est-elle valide ?

Est-ce que les morceaux ne peuvent pas rebondir plutôt que seulement glisser au sol (d’où problème de trajectoire, plus frottement visqueux proportionnel à la vitesse, pas forcément négligeable vue la taille des morceaux) ?

Je crois qu’on va être forcé d’aller lâcher des Duralex du haut de la tour Montparnasse pour de bon...
Répondre à ce message

C’est pourtant simple : expérimentation.

le 14 octobre 2011 à 17:52, par ROUX

Non, l’hypothèse n’est pas valide : la théorie de la fragmentation statistique de Nevill MOTT est très claire là-dessus.
Ces verres mathématiques qui se casseraient en des fragments assez identiques sont invoqués par la vache sphérique des mathématicien(ne)s dans une célèbre blague liée à une demande de l’INRA.
Répondre à ce message

C’est pourtant simple !

le 11 octobre 2011 à 11:45, par Jean-Baptiste

On doit pouvoir montrer que, pour un immeuble de 100 étages, ça ne sert à rien de disposer de plus de 5 verres et qu’il faudra, dans ce cas, au plus 7 coups.
Répondre à ce message

C’est pourtant simple !

le 11 octobre 2011 à 13:02, par Sylvain Barré

Effectivement, il est inutile d’avoir plus de verres que de coups d’essai. Pour un nombre d’étage donné, on peut donc se poser la question du nombre minimum de lancers (sans limiter le nombre de verres).
Répondre à ce message

C’est pourtant simple !

le 11 octobre 2011 à 23:17, par ROUX

Coquille : « Par ailleurs, ce nombre de lâchers restera indépendant de la hauteur de la tour tant que la vitesse limite des verres, due aux frottements, n’est pas atteinte ».
Répondre à ce message
C’est pourtant simple !

le 12 octobre 2011 à 11:11, par Martin Anderegg

Voici un problème qui vous intéressera peut-être. Sachant qu’il y a 128 joueurs à participer au tournoi de tennis de Rolland-Garros, combien de matchs sont joués durant la quinzaine ?
La solution (127) peut être trouvée en faisant un calcul facile (qui a le mérite d’être une possible introduction à la somme d’une suite géométrique).
Il est également possible de trouver cette solution sans aucun calcul (ou presque) à l’aide du raisonnement suivant : pour chaque match joué, un joueur est éliminé du tournoi. Il y a 128 joueurs au début du tournoi et un seul qui soulève la coupe du champion, soit 127 joueurs éliminés et donc 127 matchs.
Cette façon de résoudre le problème prend tout son sens si le nombre de joueurs au début du tournoi n’est pas une puissance de 2...
Répondre à ce message

C’est pourtant simple !

le 12 octobre 2011 à 11:53, par Sylvain Barré

C’est un peu comme découper une tablette de chocolat en petits carreaux en un nombre minimum de découpes.
Répondre à ce message

C’est pourtant simple !

le 12 octobre 2011 à 14:23, par florian

Votre remarque me fait penser à un petit jeu que j’ai découvert récemment sur Android (il soit aussi exister pour iPhone et cie). Ce jeu se nomme « slice it ! » : https://market.android.com/details?id=com.com2us.sliceit&hl=fr

Il s’agit de découper des formes géométriques (en partant d’un simple carré jusqu’à des formes beaucoup plus complexes) en un nombre exact de formes d’aires d’égales, et en un nombre déterminé de lignes droites. La difficulté est de devoir utiliser EXACTEMENT le nombre de coups de crayon qui sont imposés pour le découper en le nombre EXACT de surface qui sont imposées. Les surface peuvent ne pas avoir la même forme, mais doivent être d’aires égales.

Couper un carré en 4 en deux coups de crayon, c’est très simple. ça se corse quand il s’agit de couper un triangle équilatéral en 4 parts égales en 6 coups de crayon...

Le jeu se complique ensuite avec l’introduction de bords « non traversables » et de miroirs... de quoi se creuser les méninges un bon moment.
Répondre à ce message

C’est pourtant simple : reformulation de la solution.

le 15 octobre 2011 à 09:16, par ROUX

Que le premier verre détermine la dizaine dans laquelle le second verre cassera puis que ce second verre permette de déterminer l’unité, en partant de 1, est la solution dont il faut partir pour déterminer le nombre maximal « N » de lancers pour cette tour de nombre maximal d’étages « NMET ».
Ce ne sont plus des dizaines (une dizaine est un intervalle fixé à 10) que le premier verre va permettre de déterminer mais des intervalles variables.
Je pose « N » le nombre maximal de lancers : si j’en suis au lancer « k1 » du premier verre sans rupture à l’étage numéro E(k1), il faut que je choisisse le numéro E(k1+1) de l’étage suivant qui me permettra, en cas de rupture, de ne pas dépasser un total de N lancers avec les, au maximum, « k2 » lancers du second verre.
Donc « k1+k2=N ». Mais, « k2=k1-1 » donc « k1+(k1-1)=N ».
A ce stade, je n’ai toujours pas utilisé le nombre maximal d’étages de la tour « NMET ».
Il suffit de déterminer la valeur de E(k1) en fonction de « k1 » et cette valeur dépend de « N ».
Expérimentons un peu en lançant au premier lancer d’un étage « n »... Pour k=1, E(1)=n donc il reste (n-1) lancers. Donc pour k=2, E(2)=n+(n-1) de manière à ce qu’il ne reste plus que (n-2) lancers. Pour k=3, E(3)=n+(n-1)+(n-2) de manière à ce qu’il ne reste plus que (n-3) lancers.
Pour k=n-1, il ne reste plus que (n-(n-1)) lancers, soit un seul deuxième lancer, il faut donc que E(n-1)=n+(n-1)+(n-2)+...+(n-((n-1)+1)). Or, (n-((n-1)+1))=0. Donc E(n-1)=n+(n-1)+...+1 soit E(n-1)=(n+1).n/2.
E(n-1) est le n° de l’étage le plus haut. E(n-1)=(NMET) et n=N.
Pour déterminer N, le nombre de lancers optimisé, il faut poser ((N+1).N)/2<(NMET).

Inférieur ou égal mais je ne sais pas comment le frapper...

Les différentes valeurs des couples (N,NMET) sont (2,3) ;(3,6) etc. en passant par (14,105).

J’avais trouvé difficile la lecture de la solution sans distinguer le n° de l’étage, le nombre maximal de lancers et surtout sans clairement déterminer le numéro de l’étage du premier lancer en fonction du nombre d’étages de la tour. Ce n’était a priori pas évident pour moi que le numéro de l’étage du premier lancer était le nombre optimisé de lancers.

A priori... A posteriori, si.

J’assume que je suis à l’opposé de Pierre DELIGNE : « (...) : que rien ne reste visible de l’effort que comprendre a coûté » in LES DECHIFFREURS.
Répondre à ce message

C’est pourtant simple : reformulation de la solution.

le 17 octobre 2011 à 09:37, par Sylvain Barré

On devrait toujours donner plusieurs solutions à un même problème. Certaines en un mot, une phrase, d’autres en deux pages ou plus. Chacun y trouverait son compte. Merci pour ce commentaire !
Répondre à ce message

C’est pourtant simple !

le 17 octobre 2011 à 19:55, par ROUX

Mon propos n’est pas une autre solution : c’est la vôtre, reformulée.
J’avais un peu perdu le fil de ce sujet car votre ambition initiale était de nous amener à cette belle émotion quand on a enfin compris après s’être enfin posé la bonne question.
Or, à la lecture de la solution, je n’avais pas bien compris la bonne question qu’il fallait se poser (je ne suis toujours pas certain de m’être posé la bonne question...). Et votre lemme que vous vous contentiez d’énoncer me paraissait être une conséquence... Autant j’avais compris qu’il fallait poser qu’on devait lancer de moins en moins haut au fur et à mesure des étages, autant je n’avais initialement pas compris (et je ne comprends toujours pas comment on pouvait avoir cette idée a priori) que pour faire au plus (faute de frappe dans l’écriture du lemme) k lancers, il fallait lancer du kième étage.
Ce bel échange que vous nous avez permis d’avoir a pour écho l’article de Etienne GHYS sur la compréhension et la clarté dans lequel je ferai sous peu un commentaire en utilisant notre travail commun dans ce sujet.
Répondre à ce message

C’est pourtant simple !

le 18 octobre 2011 à 10:00, par Sylvain Barré

Il n’y a pas de faute de frappe : si vous lancez au k ième étage, l’éventualité de la casse immédiate implique que votre stratégie ne peut pas prétendre à une solution en strictement moins de k coups. Donc, si vous prétentez donner une stratégie en moins de k coups, le premier lancer doit être au plus à l’étage k et le second k-1 au-dessus du premier...

Sur les multiples solutions, j’ai un principe :
"écrire une solution c’est montrer aux autres qu’on a compris et leur
permettre d’en faire autant."
Répondre à ce message

C’est pourtant simple !

le 18 octobre 2011 à 10:37, par ROUX

Si le premier verre casse au 14éme étage, il me reste avec le deuxième verre à tester les 13 étages de 1 à 13 en partant du premier étage. 1(premier verre)+13(deuxième et au maximum)=14.

Si le premier verre casse au 27ème étage et donc au deuxième lancer, il me reste avec le deuxième verre à tester les 12 étages de 15 à 26 en partant du 15ème étage. 2(premier verre)+12(deuxième verre et au maximum)=14.

14 AU PLUS en partant de l’étage n°14 avec un premier étage numéroté n°1.

Je n’ai pas avoir évoqué une solution en strictement moins de k lancers si je lance du kième étage.

Et c’est bel et bien VOTRE solution.
Répondre à ce message

C’est pourtant simple !

le 18 octobre 2011 à 11:17, par ROUX

La fonction qui associe l’ensemble de départ des rédactions à l’ensemble d’arrivée des solutions est une surjection.
Toutes les solutions sont rédigées ; une solution peut être rédigée de plusieurs manières.
Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexion | s’inscrire | mot de passe oublié ?

L'auteur

Sylvain Barré

Maître de conférences, Université de Bretagne-Sud

[Rediffusion d’un article publié en 2011]

C’est pourtant simple !

Partager cet article

Pour citer cet article :

Crédits image :

Crédits image :

Commentaire sur l'article