Multiples particuliers

[invite4492c379]

Hello,

Un tout petit challenge que l'on m'a proposé ce week-end et que j'ai trouvé sympathique.

Montrez que dans chaque base entière b>1, chaque entier naturel n>0 possède un multiple strictement positif dont l'écriture en base b ne contient que des 0 et 1.



Dans toute la suite, tous les nombres écrits le seront en base 10, sauf s'ils sont entourés de parenthèses et dans ce cas l'indice indiquera la base utilisée pour la notation ( par exemple (1010)₂ est la notation en base 2 de 10 ).Par exemple
13 a pour multiple 1001=13*77 (composé uniquement de 0 et de 1)
(25)₁₂ a pour multiple (101)₁₂ -> 145=5*29 est un multiple de 29
(F1)₁₆ a pour multiple (10101)₁₆ -> 65793=273*241 est un multiple de 241
En base 2 c'est trivial comme toute écriture n'est composée que de 0 ou de 1 ...

-----

[invite4492c379]

Hello,

la solution :

 Cliquez pour afficher

Quelle que soit la base entière b>1 et un nombre entier strictement positif n>1 il suffit de considérer l'ensemble où est le nombre qui en base b s'écrit avec i chiffres 1 consécutifs (par exemple )
R contient n+1 nombres distincts, il y aura donc au moins deux éléments distincts de R qui auront même reste après division par n puisqu'il n'y a que n valeurs possibles pour les restes.
Il suffit d'ôter le plus petit de ces deux repunits du plus grand pour obtenir un multiple de n dont l'écriture en base b est composée uniquement de 1 et de 0.

En continuant ces manipulations on peut aisément montrer que dans chaque base entière b>1 pour chaque entier n>1 il existe un multiple m de n tel que :

* m s'écrit sous la forme (1...10...0)_b avec un nombre identique de 1 et de 0
* l'écriture de m contient exactement le même nombre d'occurences de chaque chiffres
* ...

[Deedee81]

Salut,

Tiens, j'avais lu récemment le même problème dans la rubrique divertissement du forum de l'université de Liège. En serais-tu adepte aussi ? Ou peut-être as-tu utilisé la même source que l'auteur de ce message ?

[invite4492c379]

Hello,

L'origine du problème m'est inconnue, il m'a été proposé par un ami prof qui enseigne en fac et qui aime bien proposer ce genre d'exercice pour voir la réaction des élèves ...
Je lui poserai la question à l'occasion

[A voir en vidéo sur Futura]

[invite4492c379]

J'ai la référence :

Discrete Mathematics and its Applications 6th ed.
Kenneth H. Rosen
McGraw-Hill HE
p348, Example 4

The pigeonhole principle is a useful tool in many proofs, including proofs of surprising results, such as that given in Example 4.

Example 4: Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal expansion.

Solution: Let n be a positive integer. Consider the n+1 integers 1, 11, 111, ..., 11...1 (where the last integer in this list is the integer with n+1 1s in its decimal expansion). Note that there are n possible remainders when an integer is divided by n. Because there are n+1 integers in this list, by the pigeonhole principle there must be two with the same remainder when divided by n. The larger of these integer less the smaller one is a multiple of n, which has a decimal expansion consisting entirely of 0s and 1s.

Mon ami l'a juste étendu à une base b autre que décimale. Ensuite la discussion (et l'heure, et le repas, ...) a vite dévié vers des trucs du genre «est-ce qu'il existe ... ; quel est le plus petit ... ; ... ».
Je regrette l'époque des nappes en papier si fécondes certains soirs ; les smartphones c'est quand même vachement moins pratique

Je ne fréquente pas le forum de l'université de Liège (pas encore ?). Par curiosité, la réf est-elle la même ?