Problème de math : Combien de feuilles faut-il imprimer ?

Bonjour !

Je suis vraiment mauvais en math (en fait, à part les additions… c’est à peut près tout ce que je sais faire). Par contre, je ne sais pour quelle raison, j’ai imaginé un problème à résoudre.

Etant parfaitement incapable de le résoudre, je me dit que ce serais dommage de ne pas le poster. Je sais qu’il y à des amoureux de mathématique ici, je me suis dit que ça pourrait vous amuser à essayer de résoudre ce problème. J’espère juste qu’il ne sera pas trop simple.

Le voici :

Imaginons une feuille A4 qui peut contenir 80 caractères sur la largeur (espaces compris) et 60 caractères sur la hauteur.

Un programme écrit, sur un document, les secondes écoulées toutes les secondes sur ce document, ce qui donnera la forme : "1 2 3 4 5 6 7 8 9 10 11 12 13 14 …" au bout de 14 secondes.

Sachant qu’un nombre de peut pas être sur plusieurs lignes, le programme va écrire ce nombre sur la ligne suivante (ou la page suivante sinon) si le nombre entier ne rentre pas sur la ligne actuelle.

A la fin d’un temps donné, on imprime les feuilles.

Combien de feuille il faudra imprimer (recto uniquement, mais on peut aussi calculer recto/verso si ça vous amuse, mais je pense qu’il suffira de diviser par deux) au bout de X secondes.

Par exemple, au bout de :

• 100 secondes
• 1000 secondes
• 10000 secondes
• 100000 secondes
• etc…

Voilà, en espérant que ce ne soit pas trop simple et que, surtout, le problème à résoudre soit clair.

Salut,

Il y a une espace entre chaque nombre ? Et un retour à la ligne remplace cette espace si un nombre se termine pile à la fin de la ligne ?

En tout cas, la question n’est pas forcément ultra-triviale si on veut la généraliser proprement (avec des dimensions et une base de numérotation arbitraires notamment) à cause de la condition sur le retour à la ligne. Ce qui peut être intéressant, ce serait que tu essayes toi même d’en venir à bout pour des petites valeurs avant d’essayer de généraliser. Les opérations élémentaires suffisent déjà pour dire pas mal de trucs.

Je vois pas exactement non plus ce que serait une solution. Parce que même une expression qui ne dépenderait que du nombre $n$ de secondes serait compliquée et pas forcément beaucoup moins qu’un comptage brut.

Ah bah après, je pouvais pas savoir si ce problème avait un interêt. Je les posté comme ça, au cas où. Mais si c’est nul, c’est pas grave, j’aurais essayé.

Mais dans l’idée oui, il y à un espace après chaque nombre, et le retour à la ligne remplace cet espace.

C’est pas nul, c’est juste que ça ne se prête pas facilement à la généralisation. Calculer le nombre de caractères, ça va, c’est juste sommer les ordres de grandeurs des nombres (cela dit, rien que ça ne se généralise déjà pas très bien pour obtenir une expression bien jolie). Mais en ajoutant le padding, ça devient une question de compter un peu brutalement où il faut des retours à la ligne. En exercice d’algorithmie (trouver une solution efficace jusqu’à par exemple $10^{10}$) en revanche on peut probablement s’amuser un peu avant de se heurter aux limites du problème.

EDIT : cela dit, on doit pouvoir au moins trouver un encadrement du nombre de pages pas trop mauvais.

Au bout d’un (long !) moment tu ne pourras plus rien écrire car les nombres suivants feront tous plus de 80 caractères.

Salut,

On parlait du nombre de caractère, et en testant rapidement, je me suis rendu compte qu’il y avait un motif qui se répétait. En fait, sur la séquence OEIS A117804, qui parle de la somme du nombre de chiffres des entiers inférieurs à n, on voit qu’il y a une jolie formule pour les puissances de 10 :

a(10¹) = 10. (1 * 10¹ - 0)
a(10²) = 190. (2 * 10² - 10)
a(10³) = 2890. (3 * 10³ - 110)
a(10⁴) = 38890. (4 * 10⁴ - 1110)
a(10⁵) = 488890. (5 * 10⁵ - 11110)
a(10⁶) = 5888890. (6 * 10⁶ - 111110)
…
a(10^k) = k * 10^k - R_k + 1, R_k := k-th repunit (cf. A002275)

C’est pas tout à fait le problème que l’OP pose, mais je trouve ça remarquable.

C’est un problème amusant, pas un problème nul du tout ; mais c’est plus un exercice de programmation qu’un exercice de maths.

Avec 100 feuilles (et donc 200 pages), quel sera le dernier nombre sur la dernière page ?

Variante, on utilise le séparateur des milliers, et on convient que ce séparateur occupe un demi-caractère (oui, je sais, je suis un sadique)

Aabu : cette suite est somme toute assez triviale ; Le problème est de convertir cette suite en nombre de lignes de 80 caractères, donc avec des emplacements perdus en fin de ligne.

on peut trouver facilement un majorant :
une page contient 80*60 = 4800 signes.
Par exemple, pour 1000 secondes, si on compte 4 signes par seconde, ça fait 4000 signes. Donc, avec une page, on peut avoir les résultats pour 10,100 et 1000 secondes.

Pour 10.000, il faut 9 pages au plus (40.000/4.800 = 8,333).

Après, c’est plus compliqué, il faut estimer l’effet da la longueur de ligne (80 signes).

C’est pas particulièrement difficile d’avoir une formule généralisé (moche).

La plupart des lignes vont être composés exclusivement de nombres qui ont la même taille et il est alors facile de déterminer combien de nombres tiennent dans une ligne. On défini $F(n, k)$ le nombre de nombres de taille $n$ qui tiennent dans une ligne de $k$ caractères. $m$ nombres de taille $n$ prennent $m \times (n + 1) - 1$ caractères (en comptant les espaces), donc $F(n, k)$ est le plus grand $m$ entier qui satisfait $m \times (n + 1) - 1 <= k$. Donc $F(n, k) = \Big \lfloor \frac{k + 1}{n+1} \Big \rfloor$.

On défini maintenant $G(n, k, m)$ le nombre de lignes qu’il faut pour écrire $m$ nombres de taille $n$ sur des lignes de longueur $k$. $G(n, k, m) = \Big \lceil \frac{m}{F(n, k)} \Big \rceil$. Évidemment, ce n’est valide que si $n <= k$ puisque sinon $F(n, k) = 0$.

Pour gérer les lignes mixtes, on va définir $R(n, k, m)$ qui est le nombre de caractères restant sur la dernière ligne lorsque l’on affiche $m$ nombres de taille $n$ sur des lignes de longueur $k$, en ne comptant pas l’espace qu’il faut mettre pour séparer les nombres de longueur $n$ et les suivants (ceux de longueur $n+1$). $R(n, k, m) = k - (m \mod F(n, k)) \times (n + 1)$. En utilisant ça, on peut trouver le nombre de nombre de taille $n+1$ qui peuvent tenir sur la dernière ligne (potentiellement incomplète) des nombres de taille $n$: $F(n+1, R(n, k, m))$.

Il nous faut encore une dernière fonction pour déterminer combien de nombre de taille $n$ restent à imprimer une fois que l’on a utilisé ce qu’il reste de la ligne qui fini les nombres de taille $n-1$, en supposant qu’on veuille tous les afficher. $M(1, k) = 9$ et $M(n, k) = 10^n - 10^{n-1} - F(n, R(n-1, k, M(n-1)))$.

Au bout de $x$ secondes et sur des feuilles de largeur 80 et hauteur 60, on a donc imprimé ${\displaystyle \left\lceil\frac{\left(\sum _{n = 1}^{\lfloor\log_{10}{x}\rfloor} G(n, 80, M(n, 80)) \right) + G(\lceil\log_{10}{x}\rceil, 80, M(\lceil\log_{10}{x}\rceil, 80) - 10^{\lceil\log_{10}{x}\rceil} + x + 1)\times(\lceil\log_{10}{x}\rceil - \lfloor\log_{10}{x}\rfloor)}{60}\right\rceil}$ feuilles.

Je vois pas ce qu’il y a de si compliqué

J’ai comparé le résultat de la formule avec celle d’une fonction vraiment simple pour toutes les valeurs entre 2 et 2000 et ça colle, donc la formule est probablement correcte (mis à part pour 1 qui appelle $M(0, 80)$ qui n’est pas défini).

Et pour donner un peu de piquant à l' affaire, il reste à envisager les subtilités que le chiffre 1 apporte au problème selon que l’on utilise une police proportionnelle ou pas