generated from Timothee/TFJM-Template
40 lines
2.5 KiB
TeX
40 lines
2.5 KiB
TeX
\section*{Eléments de réponse}
|
|
|
|
\q (Facile) $a + b - \operatorname{pgcd}(a,b)$.
|
|
|
|
\q (Moyen) Comprendre qu'il y a un sommet commun et traiter la question suivante.
|
|
Deux réponses équivalentes possibles:
|
|
\[ \sum_{d | a \text{ ou } d | b \text{ ou } d | c} \varphi(d)\]
|
|
ou utiliser la formule du crible pour obtenir
|
|
\[a+b+c-\operatorname{pgcd}(a,b) - \operatorname{pgcd}(a,c) - \operatorname{pgcd}(b,c) + \operatorname{pgcd}(a,b,c).\]
|
|
|
|
Ce qui est difficile, c'est de voir qu'on ne peut pas atteindre
|
|
\[a+b+c-\operatorname{pgcd}(a,b) - \operatorname{pgcd}(a,c) - \operatorname{pgcd}(b,c)\]
|
|
|
|
%\q Il est possible de faire en sorte que les graduations $a$ et $b$ se rencontrent et $b$ et $c$ se rencontrent sans que $a$ et $c$ ne se rencontrent si, et seulement si, $b \not| \operatorname{pgcd}(a,c)$. Quitte à permuter, on suppose $\operatorname{pgcd}(a,c) < \operatorname{pgcd}(a,b) < \operatorname{pgcd}(b,c)$.
|
|
%Le minimum est alors $a+b+c - \operatorname{pgcd}(a,b) - \operatorname{pgcd}(b,c)$.
|
|
|
|
\q (Facile) $G^p = 1 + \sum_{i=1}^N (p_i -1)$\\
|
|
(Trivial) $G^g = a^{N-1}$\\
|
|
(Moyen) $G^c = \sum_{i=1}^N \varphi(i)$ où $\varphi$ est l'indicatrice d'Euler\\
|
|
(Trivial) $G^d = \alpha_N$
|
|
|
|
\q (Facile) Le cas $N=3$ est la question $2$.
|
|
|
|
(Difficile) On ne peut pas faire mieux pour $N=4$. C'est facile si le graphe des intersections deux à deux n'est pas un cycle. Sinon, il faut distinguer les cas et utilise le fait qu'un nombre premier est toujours $\geqslant 2$ pour conclure.
|
|
|
|
(Ouvert) pour $N\geqslant 5$, on pense qu'on ne peut pas faire mieux.
|
|
|
|
\q (Moyen) $2$ (faire des intersections consécutives);
|
|
(Facile) $2$ car $\sum_{k=0}^{N-2} a^k < a^{N-1}$;
|
|
(Ouvert) $\Theta(\log_2(N))$?
|
|
(Difficile/Ouvert) $1+$ nombre de facteurs premiers de $\alpha_N$?
|
|
|
|
\q(Difficile) Remarque: $\alpha_N$ est la suite donnée par https://oeis.org/A005179
|
|
Elle n'est pas facile à calculer à cause des entiers \og extraordinaires \fg{} mais on peut quand même la minorer asymptotiquement par $(\log_2 N)^{\log_2 N)}$.
|
|
|
|
Réponse: $G^p_N = G^p_N \sim \Theta(N^2 \ln(n)^3)$,
|
|
$G^g_N = a^{N-1}, G^c_N \sim \frac{N^2}{2\zeta(2)}$ et $G^d_N \sim \Theta((\log_2 N)^{\log_2 N})$ donc
|
|
\[\widehat{G}^c_N < G^c_N \ll G^p_N \ll G^d_N \ll G^g_N.\]
|
|
|
|
\q (Difficile/Ouvert) Oui, on choisit une permutation $\sigma \in \operatorname{Bij}(\mathbb{N})$ telle que la suite $n\mapsto \varphi(\sigma(n))$ est croissante. La suite $u_n = \sigma(n)$ convient alors. En fait, c'est la seule qui réalise le minimum asymptotique, au choix de $\sigma$ près. Je ne sais pas le démontrer (utilise l'hypothèse de Riemann?) |