Un problème de Paul Erdos

Zaineb222 · July 2017

Je suis tombée sur un exercice proposé par Paul Erdos et je ne sais pas s'il a été résolu ou si c'est une conjecture (j'ai vu qu'il était présent dans une liste de "problem unsolved") mais je ne trouve rien sur cette propriété sur internet et puis je n'arrive pas à la démontrer. Bref voici le problème en question.

Montrer que tout nombre inférieur à n! peut être écrit comme somme d'au plus n diviseurs de n!

Tonm · July 2017

C'est direct tu rend à présenter les $x\ge \frac{n!}{2}$ et $x=\frac{n!}{2}+a$ (ça suffit)

Je te laisse voir comment roule $a$ mais c'est assez simple.

depasse · July 2017

@Tonm,

Si c'est direct et simple, ce n'est pas une conjecture d'Erdös

Tonm · July 2017

Ah, c'est une conjecture? je ne sais pas...

Vous ne voyez pas $a$ ça peut être quoi? Je doute que c'est une conjecture, d'ailleurs le topic n'a pas dit la source entière.

uvdose · July 2017

@Tonm : pourrais-tu être plus clair ?

Tonm · July 2017

En ce moment je ne pense pas dans 24 heures oui (je poste ce que j'ai pensé)
Cordialement.

Tonm · July 2017

Euh. Prenons $x\le n!$
si $x=n!=\dfrac{n!}{2}+\dfrac{n!}{2}$ et si $\dfrac{n!}{2}<x=\dfrac{n!}{2}+a<n$

$a=(n).(\frac{(n-1)!}{2}-i) +j $ pour un certain $i$,

$j\le n-1$
On part disons de $n=4$ puis par récurrence?

P.S. somme d'au plus $n-1$ diviseurs de $n!$; ($n>1$).

uvdose · July 2017

Pas évident de décrypter tes messages, Tonm...
En utilisant un ingrédient qu'il me semble avoir discerné dans ta recette, voilà ce que je propose :

Notons $\mathcal{P}(n)$ la proposition de Zaineb222, qu'on va effectivement prouver par récurrence.
- $\mathcal{P}(1)$ est clairement vraie.
- Supposons que $\mathcal{P}(1),\cdots,\mathcal{P}(n)$ soient vraies pour un certain entier $n\geqslant1$ ; soit $x$ un entier tel que $1\leqslant x\leqslant (n+1)!$. On écrit la division euclidienne de $x$ par $n+1$ : on a $x=(n+1)k+r$, avec $k\leqslant n!$ et $0\leqslant r<n+1$. Par hypothèse de récurrence, $k$ s'écrit comme la somme d'au plus $n$ diviseurs de $n!$, donc $x=(n+1)k+r$ s'écrit comme la somme d'au plus $n+1$ diviseurs de $(n+1)!$, ce qui prouve que $\mathcal{P}(n+1)$ est vraie.

Comme depasse, ça m'étonnerait beaucoup qu'il s'agisse d'une conjecture d'Erdös non résolue ;-)

uvdose · August 2017

1) Je viens de voir le PS de Tonm... Effectivement, en adaptant la démonstration précédente, il n'est pas difficile de prouver que lorsque $n\geqslant2$, tout entier dans $[\![1,n!]\!]$ s'écrit comme la somme d'au plus $n-1$ diviseurs de $n!$.

2) En regardant comment fonctionne la récurrence, on obtient par exemple une décomposition de $n!-1$ :

$n!-1=\sum\limits_{k=1}^{n-1}k\dfrac{n!}{(k+1)!}$ ,

formule classique. Mais quelqu'un voit peut-être un moyen encore plus simple de décomposer $n!-1$ ?