Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 16-01-2018 18:43:10

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3489

Discours sru un modulo.

Bonsoir @ tous.

Les k premiers multiples d'un entier " a " modulo " b ", a < b et a, b premiers entre eux, peuvent ils être groupés sur un intervalle de k unités, k < b-1 ?
Autrement dit, peuvent ils être tous voisins ?

C'est évident si a = + ou - 1 modulo " b ", et ça semble impossible dans le cas contraire.

Est ce vraiment impossible ?



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 16-01-2018 19:09:55

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,801E+3

Dsicours sur un modulo.

Bonsoir, je n'ai pas compris la question... tu pourrais donner un exemple (ou un contre exemple ) ?

Par exemple pour  a et b premiers : (11,22,33,44,55,66,77) mod7 = (4,1,5,2,6,3,0) ce sont bien toutes les unités de 0 à 6.

pour 24 et 5 , elles sont consécutives décroissantes (comme pour toute factorielle avant un nombre premier) .

Qu'est-ce qui semble impossible ?  De les avoir croissantes ?

 #3 - 17-01-2018 07:54:36

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3489

siscours sur un modulo.

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 ?

 #4 - 17-01-2018 09:46:25

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,801E+3

Discours su un modulo.

Ben, désolé, mais je ne comprends toujours pas... Pour 7 [22], comme tu dis, de la même manière que pour tous nombres premiers entre eux, les 21 premiers multiples occupent les 21 premières unités.

Edit : ah, oui, k<b-1...

 #5 - 31-01-2018 10:06:14

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3489

Discourss sur un modulo.

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.

 #6 - 31-01-2018 12:00:31

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 765

Discours ur un modulo.

Je cherche toujours !...
Je crois que je vais arriver à le prouver pour k=5 (humour).
Je n'ai pas encore de preuve complète pour k quelconque.

 #7 - 31-01-2018 13:55:47

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3489

Discoours sur un modulo.

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....

 #8 - 31-01-2018 13:58:27

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3489

Discurs sur un modulo.

masab a écrit:

Je cherche toujours !...
Je crois que je vais arriver à le prouver pour k=5 (humour).
Je n'ai pas encore de preuve complète pour k quelconque.

Ma solution passe par une quasi-absence de calcul.
Elle ne fait appel à une quelconque récurrence.

 #9 - 01-02-2018 09:40:24

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 734

Discours sur u nmodulo.

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

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.

 #10 - 01-02-2018 17:26:29

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3489

Discours sur un modulo..

Il m'est aussi arrivé de nombreuses fois, dans mon travail, après avoir cogité vainement sur un problème ardu de longues heures, d'avoir la solution immédiate le lendemain matin au réveil. La nuit de sommeil avait littéralement remis dans l'ordre les idées éparpillées et confuses. Est ce que j'aurais dû demander une prime à mon patron pour ce travail nocturne ?

 #11 - 01-02-2018 18:43:04

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 734

discours sur un lodulo.

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.

 #12 - 02-02-2018 07:55:46

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3489

Discours sur un modulo..

ça me va Ebichu.

Une petite réserve: tu indiques que le premier intervalle contient {0,a....(k-1)a}
En fait c'est peut être dû au non dit de l'énoncé. Pour moi, il est évident que le 1er multiple de a est a, vu que le 0 [b] est le dernier. ça laisse plus de marge pour trouver l'éventuel intervalle en question.  Mais bon ça ne change rien à l’homogénéité de ton raisonnement.

 #13 - 02-02-2018 08:02:18

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3489

discourq sur un modulo.

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.

 #14 - 02-02-2018 19:26:05

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 734

Discours sur nu modulo.

En effet, commencer à 0 ou a ne change rien à mon raisonnement.

Quoi qu'il en soit, c'est un résultat qui est assez facile à intuiter, mais plutôt casse-pieds à démontrer...

 #15 - 03-02-2018 10:52:03

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 765

discours sur un modulp.

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.

 #16 - 03-02-2018 16:40:28

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3489

Disours sur un modulo.

C'est une variante à Ebichu tout à fait convenable également ! Bravo à toi Masab.

 #17 - 05-02-2018 10:56:57

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3489

Discours sur uun modulo.

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é.

 #18 - 07-02-2018 14:26:18

masab
Expert de Prise2Tete
Enigmes résolues : 44
Messages : 765

iscours sur un modulo.

A nodgim : ta preuve #17 me semble tout à fait correcte et particulièrement courte et simple !

 #19 - 07-02-2018 15:22:51

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3489

discours sir un modulo.

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....

 #20 - 11-02-2018 08:07:48

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3489

Discours sur u modulo.

Une nouvelle preuve courte (je vous l'ai dit, il y en a beaucoup) donnée sur un site voisin :

Si les k premiers multiples de " a " forment un intervalle, alors tous les autres forment un intervalle complémentaire. Or ce complémentaire ne peut dépasser " a " unités, car sinon, au plus tard lorsque n*a dépasse b, un multiple de l'intervalle tomberait dans ce complémentaire. Mais ce complémentaire ne peut être moindre que " a " puisque le multiple suivant l'un quelconque d'entre eux serait en dehors de celui-ci.

Contradiction.

 #21 - 13-02-2018 20:05:13

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 734

Discours sur un modulo

Joli smile

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete