Pardon Gwen, une imprécision dans l'énoncé. Il faut bien entendu a < b .

Par exemple 7 modulo 22 : les 4 premiers multiples de 7 [22] soit : 7, 14, 21, 6 n'occupent pas un intervalle de 4 unités consécutives, comme 7 à 10 par exemple, loin s'en faut. Et c'est intuitivement évident.

Du coup, on peut tenter le coup avec, par exemple, les 15 premiers multiples, et tu verras que ça ne marche pas non plus.

Mais est ce bien toujours vrai, et si oui comment le prouver ?

Pas d'amateurs ?

C'est un pur exercice de style, niveau Lycée.

La réponse est assez évidente, la preuve est assez courte mais nécessite de recourir à une astuce. Néanmoins, je pense qu'il doit y avoir plus d'une preuve.
ça reste de l'arithmétique de base.

Ah oui, Masab, c'est parce que ça traînait un peu ici que j'ai tenté ma chance là où tu sais. Sans guère plus de succés....

Je cherche aussi. Là, j'ai une preuve dans le cas où (a-1) et (a+1) sont premiers avec b, pas loin

Edit : ça y est, j'ai trouvé. Mais je suis au boulot, je mettrai la preuve ce soir...
Bizarre comme le cerveau est souvent plus efficace quand il est occupé à autre chose.

Voici ma preuve.

Spoiler : [Afficher le message] Supposons que les k premiers multiples de a sont groupés sur un intervalle du type [x;x+k-1] (il faut comprendre un intervalle modulo b : par exemple, si b=10, alors [7;2]={7;8;9;0;1;2} est un intervalle). On ajoute "a" à ces k premiers multiples, et par translation, on obtient un autre intervalle "groupé" de longueur k-1.

Or ces deux intervalles contiennent l'un {0;a;...;(k-1)a} et l'autre {a;2a;...;ka}, ils ont donc k-1 nombres en commun. Ce n'est possible que si le deuxième intervalle est [x+1;x+k], ou [x-1;x+k-2].

Dans le premier cas, le seul nombre n'appartenant qu'au 2e intervalle est ka, donc ka=x+k (les égalités étant sous-entendues modulo b). On réalise à nouveau la même opération, en ajoutant "a" au deuxième intervalle, le troisième intervalle est alors [x+2;x+k+1], et on en déduit que (k+1)a=x+k+1. De ka=x+k et (k+1)a=x+k+1, on tire a=1.

Dans le deuxième cas, on obtient de même ka=x-1 et (k+1)a=x-2, d'où on tire a=-1.

Je suis sûr qu'il existe plus d'une preuve pour résoudre ce problème. Celle d'Ebichu et la mienne, ça fait 2. Il doit sûrement y en avoir des tas d'autres....



--------------------------------------------------------------------------------

Dans quelle condition la suite des k premiers multiples de a modulo b, a et b premiers entre eux, se serrent dans un intervalle de k unités, k < b-1 ?

On exclut les cas triviaux a = + ou - 1 qui est solution.

1)
Si a < b/2 : Les 3 premiers multiples de "a" nous indiquent que k doit être > a.   
Si a > b/2 : entre j(-a) dont la valeur absolue ne dépasse pas b  et (j+1)(-a) dont la valeur absolue dépasse b , il y a j+1 multiples de "a" dans un intervalle de longueur " a+1 ".
Donc il faut k > a.   

2)
A contrario, la zone hors intervalle k est < a  sinon c'est au plus tard le premier multiple de " a " qui dépasse " b " qui tombe hors intervalle k si a < b/2 ou le 3 ème multiple de "-a" si a > b/2.

3)
Les b premiers multiples de " a " modulo b ( de (1 * a) à (b * a)) prennent chacun une des valeurs de 0 à b-1.

4)
En sectionnant [1,a*b] en "a" intervalles de b unités, on observe dans chaque intervalle b l'intervalle k. 
C'est dans le dernier intervalle b ( ](a-1)b, ab] )  qu'on trouve le dernier intervalle k, et on y place encore au moins 1 multiple de "a" puisque k > a. Il faut donc aller jusqu'au dernier intervalle k pour remplir complétement k. A contrario, après ce dernier intervalle k, on trouvera au mieux un dernier multiple de "a" qui tombe en dehors de k, voir 2). Pour remplir l'intervalle k, il faut donc placer au minimum b-1 multiples de " a ", donc placer avant le dernier multiple de "a" qui termine de remplir l'intervalle k : (b-k-1) multiples de "a" dans les masques. Pour avoir b-k-1 = 0 il faut k = b-1, contraire à l'énoncé.

Donc pas de solution.

On va prouver que l'énigme a une réponse négative pour tous les triplets [latex](a,b,k)[/latex].

D'abord on remarque que les éléments de la suite [latex](a, 2a,..., (b-1)a,0)[/latex] sont deux à deux distincts[latex]\mod b[/latex].
En effet soient des entiers [latex]i,j\in [[1,b]][/latex] tels que [latex]ia\equiv ja\mod b[/latex] ; alors [latex]b[/latex] divise [latex](i-j)a[/latex] et comme [latex]b[/latex] est premier avec [latex]a[/latex], on a [latex]b[/latex] divise [latex]i-j[/latex], c-à-d [latex]i\equiv j\mod b[/latex] d'où [latex]i=j[/latex].

On suppose [latex]3\leq k \leq b-2[/latex]. On suppose aussi que l'énigme a une réponse positive pour le triplet [latex](a,b,k)[/latex], c-à-d que [TeX]I=\{a,2a,...,ka\}[/TeX] est une partie groupée.

Sur une idée de Ebichu, en ajoutant [latex]a[/latex] aux éléments de [latex]I[/latex] on obtient la partie groupée [TeX]J=\{2a,3a,...,ka,(k+1)a\}[/TeX] et on considère l'intersection [TeX]I\cap J=\{2a,3a,...,ka\}\,.[/TeX] On a [latex]|I\cap J| = k-1 \leq b-3[/latex] ; [latex]I\cap J[/latex] est une partie groupée, sinon on ne pourrait pas la prolonger en une partie groupée par l'adjonction d'un élément, de deux façons différentes.

En retranchant [latex]a[/latex] des éléments de [latex]I\cap J[/latex] on obtient la partie groupée [TeX]\{a,2a,...,(k-1)a\}\,.[/TeX] Par suite l'énigme a une réponse positive pour le triplet [latex](a,b,k-1)[/latex].

Par récurrence on en déduit que  l'énigme a une réponse positive pour le triplet [latex](a,b,2)[/latex]. Autrement dit [latex]\{a,2a\}=\{u,u+1\}[/latex] où [latex]u[/latex] est un entier ; donc [latex]a=1[/latex] ou [latex]a=-1[/latex], ce qui est exclu. Ceci achève la preuve.

Une autre preuve plus courte (à force de tourner et retourner le truc...).

L'intervalle des k nombres contient " a " mais ne chevauche pas " 0 " le zéro étant le dernier multiple.
Si "a" n'est pas extrémité d'intervalle, alors celui ci contient a+1 et a-1, mais du coup +1 et -1 qui arrivent juste avant a+1et a-1 : L'intervalle est donc b entier sauf 0.
Si " a " est extrémité d'intervalle contenu dans [1 ; a], alors il faut placer a-1, donc -1 juste avant, qui est hors intervalle de l'hypothèse.
Si " a " est extrémité d'intervalle contenu dans [a;b-1], alors il faut placer a+1, donc +1 juste avant, qui hors intervalle de l'hypothèse.

L'intervalle est donc b sans le 0, contraire à l'énoncé.

Oui, je trouve aussi !

Il y a sans doute encore d'autres preuves.

Une autre piste, qui reflète au plus près la répartition des multiples de "a" est qu'il existe au plus 3 différents écarts entre les multiples de "a" voisins, ces écarts allant décroissants et passant obligatoirement par 1 ( en fait nouvel écart = reste (plus ancien écart) / (plus récent écart) ). Le plus ancien écart disparait avant la création du nouvel écart. Sur le final, il ne reste que l'écart 1. Ce qui de facto prouve la conjecture.
Bon maintenant la mise en forme n'est pas forcément simple....

Joli