Exo arithmétique (olympiades)

[erff]

Bonjour, je voudrais de l'aide pour finir un exo.


Soit E={1,2,...,280}
Quel est le plus petit entier n, qui est tel que toutes partie de E à n éléments possède 5 nombres 2 à 2 premiers entre eux.


Mon début de solution :

Pour moi, il faut chercher le nombre qui admet le plus de nombre non premiers avec lui...On pense à calculer 2*3*5*7=210 qui semble être un bon candidat.
Un petit calcul (formule du crible de Poincarré) nous dit qu'il y a 216 nombres qui ne sont pas premiers avec 210...

Conclusion


Cependant je n'arrive pas à montrer que 217 convient (ou pas) (c'est là que je demande votre aide).


Merci

[homotopie]

Je ne vois pas pourquoi s'attacher plus particulièrement à 210. Le problème n'est pas "dans une partie P de cardinal n il faut que tout nombre de cette partie P, exemple 210, soit premier avec un autre nombre de cette partie P".
Autrement dit, s'il y a 217 nombres, il y en a certainement de plus intéressants que 210.
Ceci dit tu n'es pas loin de la réponse à mon avis mais c'est plus de la coïncidence qu'autre chose.

Il faut appliquer le principe des tiroirs.
multiples de 2 : ?
multiples de 3 mais pas de 2 : ?
multiples de 5 mais pas de 2 ni de 3 : ?
...
nos tiroirs sont formés en considérant le plus petit premier divisant le nombre (1 est mis dans un tiroir tout seul, il est pratique il est premier avec tout le monde).
Pour trouver un minorant, le principe s'applique sans trop de difficultés.

Dans le sens inverse, on compte le nombre de premiers,
si 5 premiers distincts (terminé)
Ensuite en supposant qu'il y ait moins de 4 premiers, minorer les tiroirs "2", "3", "5", et "7". Il y a toujours un nombre N qui est premier ou produit de premiers autres que 2, 3, 5 et 7. 5 (ce produit ne peut pas en contenir beaucoup).
Puis montrer que dans le tiroir "7", il y en a assez pour en choisir un M qui est premier avec N.
Puis dans le tiroir "5", il y en a assez pour en choisir un qui est premier avec M et N.
...

[homotopie]

Hier, je n'avais qu'une idée (la flemme de vérifier les détails est partie aujourd'hui).
C'est bien 217 (mais 210 ne joue pas de rôle particulier, la "coïncidence" étant que la somme des tiroirs de "2" à "7" est égal au cardinal des nombres non premiers avec le produit (210) de ces 4 premiers).
Le sens inverse est un petit peu plus compliqué que ce que je n'ai indiqué mais l'esprit reste bien là : faire des sous-tiroirs dans les tiroirs pour obtenir des nombres premiers 2 à 2 avec les nombres d'ores et déjà choisis.

Je trouve cette méthode un peu compliquée pour une olympiade mais je n'ai pas trouvé plus simple.

[erff]

Bonjour,

merci d'avoir répondu


PS : c'est tiré d'une olympiade internationale il me semble

[homotopie]

Un corrigé de ma pomme si ça t'intéresse (ou quelqu'un d'autre) :

 Cliquez pour afficher

On commence par fabriquer des tiroirs
On pose pour un premier p<280 E(p)={1<=n<=280 ; p est le plus premier dans la décomposition de n}. E(1)={1}.
Les E(p) sont trivialement disjoints. Deux nombres dans un même E(p) ne sont pas premiers entre eux car cela implique p distinct de 1 et divise ces deux nombres. (la réciproque est évidemment fausse).

E(2) :
ce sont les nombres pairs, il y en a 280/2=140
E(2) contient 8 puissances de 2 {2,4,8,16,32,64,128,256} et au moins 12 nombres de la forme 2q, q premier>2}, par exemple pour les premiers dans {3,5,7,11,13,17,19,23,29,31,37 ,41}.

E(3) :
ce sont les nombres impairs multiples de 3, il y en a 1 pour chaque intervalle de la forme [l 6k+1,6k+6 l], à savoir 6k+3, d'où (1/6)x276+ 1 (pour 279)=47.
E(2) contient 5 puissances de 3 {3,9,27,81,243} et au moins 13 nombres de la forme 3q, q premier>3}, par exemple pour les premiers dans {5,7,11,13,17,19,23,29,31,37,4 1,43,47}.

E(5) :
ce sont les nombres multiples de 5 premiers avec 2 et 3, il y en a 2 pour chaque intervalle de la forme [l 30k+1,30k+30 l], à savoir 30k+5 et 30k+25, d'où (2/30)x270+ 1 (pour 275)=19.
E(3) contient 3 puissances de 5 {5,25,125} et 13 nombres de la forme 5q, q premier>5}, à savoir les premiers dans {7,11,13,17,19,23,29,31,37,41, 43,47,53}.
280/7=40 donc pour p>=7, un nombre dans E(p) est de la forme pq avec q=1 ou q premier>=p.

E(7) contient 2 puissances de 7 {7, 49} et 8 produits 7xq, q est dans {11,13,17,19,23,29,31,37}. En effet 7³=343>280 et 7x41=287<280. Le cardinal de E(7) est égal à 2+8=10.
L'union disjointe E'' de ces 4 E(p) a un cardinal égal à 140+47+19+10=216.
L'union des E(p) pour p distinct de 2, 3, 5 et 7 est noté E'.

E(11) contient 2 puissances de 11, 11 et 121=11², et 4 produits 11q : 11x{13,17,19,23}. En effet, 11³>7³>280 et 11x29=319>280. Le cardinal de E(11) est égal à 2+4=6.

E(13) contient 2 puissances de 13, 13 et 169=13², et 2 produits 13q : 13x{17,19}. En effet, 13³> 7³>280 et 13x23=299>280. Le cardinale de E(13) est égal à 2+2=4.

E(p, p>13)
17²=289>280 donc les autres E(p) ne contiennent que le premier p.


Il existe une partie de cardinal 216 ne contenant pas 5 nombres premiers 2 à 2 : E''.
On a vu que E '' est de cardinal 216. Maintenant, soient 5 nombres dans cette partie, ils se répartissent dans les 4 ensembles E(2), E(3), E(5) et E(7). Un des ces E(p) en contient donc au moins 2 qui ne peuvent être premiers entre eux.

Une partie P de cardinal 217 contient toujours 5 nombres entre eux.
On distinguera les cas « moins de 8 dans E' », « entre 9 et 13 dans E' », « au moins 14 dans E' ».

1er cas : il y a moins de 8 éléments de P dans E'.

Comme 217>card(E''), il en existe au moins un élément de P, noté N(1), qui est dans E'. Il est produit au plus de deux premiers distincts. Il suffit donc d'être non multiples d'au plus deux premiers p(1) et p(2) (>=11), pour être premier avec N(1).

Il y a au moins 217-8=209 éléments dans E' de cardinal 216=209+7. Pour chaque partie contenue dans E', au plus 7 ne sont pas dans P.

Il y a au moins 10-7=3 éléments de P dans E(7). Au plus, deux sont multiples de p(1) et de p(2), càd au plus deux sont non premiers avec N(1). Il y a donc au moins un élément, noté N(2), de E(7) qui soit premier avec N(1). Ce nombre est produit d'au plus deux premiers distincts notés p(3) et p(4). Il suffit donc d'être non multiples d'au plus 4 premiers(>=7) pour être premier avec N(1) et N(2).

Il y a au moins 16-7=9 éléments de P dans E(5) qui sont des puissances de 5 ou de la forme 5x(premier>5). Au plus, 4 sont multiples d'un des p(i), i=1, 2, 3 ou 4, càd au plus 4 sont non premiers avec N(1) ou avec N(2). Il y a donc au moins un élément, noté N(3), de E(5) qui soit premier avec N(1) et N(2). Ce nombre est produit d'au plus deux premiers distincts notés p(5) et p(6). Il suffit donc d'être non multiples d'au plus 6 premiers(>=5) pour être premier avec N(1), N(2) et N(3).

Il y a au moins (5+13)-7=11 éléments de P dans E(3) qui sont des puissances de 3 ou de la forme 3x(premier>3). Au plus, 6 sont multiples d'un des p(i), i allant de 1 à 6, càd au plus 6 sont non premiers avec un des N(j), j=1, 2 ou 3. Il y a donc au moins un élément, noté N(4), de E(3) qui soit premier avec chaque N(j).

Il y a au moins 8-7=1 puissance de 2 dans P. Ce nombre N(5) est premier avec chaque N(j), j allant de 1 à 4. Les nombres N(1), N(2), N(3), N(4) et N(5) ainsi choisis conviennent.

2ème cas : il y a entre 9 et 14 éléments de P dans E'.

Il y a au moins deux nombres premiers entre eux de P dans E' et qui, de plus, sont soit une puissance d'un premier soit égal à 1.
Il y a au moins trois nombres qui sont une puissance d'un premier>=11 (ou égal à 1) dans P.
En effet, les nombres qui ne sont pas ainsi sont en nombre de 4 dans E(11), en nombre de 2 dans E(13). Donc il y en au moins 3 de ce type. Pour être non premiers entre eux, ils doivent être une puissance d'un même premier, mais de telles puissances pour un premier donné sont au plus 2 car le premier est au moins égal à 11. Par mi ces 3 nombres, il y en a donc au moins deux premiers entre eux.
Ces nombres sont notés N(1) et N(2). Il suffit d'être non multiple d'au plus deux premiers p(1) et p(2) pour être premier 2 à 2 avec N(1) et N(2).

Il y a au moins 217-14=203 éléments dans E' de cardinal 216=203+13. Pour chaque partie contenue dans E', au plus 13 ne sont pas dans P.

Il y a au moins 16-13=3 éléments de P dans E(5) qui sont des puissances de 5 ou de la forme 5x(premier>5). Au plus, 2 sont multiples d'un des p(i), i=1, 2, 3 ou 4, càd au plus 2 sont non premiers avec N(1) ou avec N(2). Il y a donc au moins un élément, noté N(3), de E(5) qui soit premier avec N(1) et N(2). Ce nombre est produit d'au plus deux premiers distincts notés p(3) et p(4). Il suffit donc d'être non multiples d'au plus 4 premiers(>=5) pour être premier avec N(1), N(2) et N(3).

Il y a au moins (5+13)-13=5 éléments de P dans E(3) qui sont des puissances de 3 ou de la forme 3x(premier>3). Au plus, 4 sont multiples d'un des p(i), i allant de 1 à 4, càd au plus 4 sont non premiers avec un des N(j), j=1, 2 ou 3. Il y a donc au moins un élément, noté N(4), de E(3) qui soit premier avec chaque N(j). Ce nombre est produit d'au plus deux premiers distincts notés p(5) et p(6). Il suffit donc d'être non multiples d'au plus 6 premiers(>=3) pour être premier avec N(1), N(2) N(3) et N(4).

Il y a au moins (8+12)-13=7 éléments de P dans E(2) qui sont des puissances de 2 ou de la forme 2x(premier>2). Au plus, 6 sont multiples d'un des p(i), i allant de 1 à 6, càd au plus 6 sont non premiers avec un des N(j), j=1, 2, 3 ou 4. Il y a donc au moins un élément, noté N(5), de E(2) qui soit premier avec chacun de ces N(j).
Les nombres N(1), N(2), N(3), N(4) et N(5) ainsi choisis conviennent.

3ème cas : il y a au moins 15 éléments de P dans E'.
E(11) et E(13) en contiennent au plus 6+4=10, il y a donc au moins 5 nombres premiers>13 (ou égal à 1) qui sont premiers entre eux.

[erff]

Eh bien merci beaucoup pour cette preuve détaillée

Je relirais tout ça sérieusement demain (j'ai les yeux qui collent là )