Partition de N*

[Anonyme]

Bonjour,

Un petit énoncé simple, mais je ne sais par où partir...

On se donne deux réels strictement positifs a et b et l'on pose
A={partent(n*a), n>0} et B={partent(n*b), n>0}.
On demande une condition nécessaire et suffisante très simple
portant sur a et b pour que A et B forment une partition de N*.

Auriez-vous une indication ?
D'avance merci.

Iulius

[Anonyme]

On 2004-10-27, Iulius wrote:
> Bonjour,
>
> Un petit énoncé simple, mais je ne sais par où partir...
>
> On se donne deux réels strictement positifs a et b et l'on pose
> A={partent(n*a), n>0} et B={partent(n*b), n>0}.
> On demande une condition nécessaire et suffisante très simple
> portant sur a et b pour que A et B forment une partition de N*.
>
> Auriez-vous une indication ?
> D'avance merci.

Ouh, c'est un classique. Un premier indice : au pifomêtre, la « densité »
des partent(n*a) dans N (ça y en a pas être très formalisé, m'enfin avec
les mains, ça se comprend) est 1/a, et celle des partent(n*b) est 1/b.
Il serait donc de bon ton que 1/a + 1/b = 1. Dans ce sens, ce n'est pas
trop difficile à prouver (i.e. si {A, B} partitionne N*, alors
1/a+1/b=1). Par contre, la réciproque est un peu plus délicate.

(Pour information, il me semble que ce résultat porte le nom de théorème
de Beatty).

--
Frédéric

[Anonyme]

Bonjour,

> Ouh, c'est un classique.
> (Pour information, il me semble que ce résultat porte le nom de théorème
> de Beatty).

Ah oui, désolé pour le dérangement. Et merci pour la référence.

J'ai trouvé dans les archives Google :



Avec les mots sturmiens :

http://www-igm.univ-mlv.fr/~berstel/Articles/magdeburg.ps.gz



D'après " Concrete Mathematics" de Graham, Knuth et Patashnik
(Addison-Wesley) , livre que je recommande par ailleurs inconditionnellement
(en dépit de son prix), ce serait dû à Lord Rayleigh (1877). Une démo figure
dans le bouquin, mais je vois que tu as déjà eu des réponses. La réciproque
est vraie:

Pasant S(a) ={E(a.n)}(n\in N-{0}) (donc S(a) est l'ensemble des parties
entières des multiples non nuls de a), on a (S(a), S(b)) partition de N si
et seulement si a et b sont positifs, irrationnels, et si 1/a+1/b=1




Les deux ensembles sont disjoints:

Si n = E(k.x) = E(l.k)
alors

n = 1 ne s'écrit pas E[k.x], soit k tel que

n (k - 1) x
D'après l'hypothése sur n, on a

n+1 k - 1
(n+1) (1 - 1/y) n - k + 1

n 1 et y > 1.

(Dominique Bernardi)



Iulius

[Anonyme]

Bonjour,

Iulius a écrit:
> Bonjour,
>[color=green]
>> Ouh, c'est un classique.
>> (Pour information, il me semble que ce résultat porte le nom de théorème
>> de Beatty).
>
>
> Ah oui, désolé pour le dérangement. Et merci pour la référence.
> J'ai trouvé dans les archives Google :
> http://www-igm.univ-mlv.fr/~berstel/Articles/magdeburg.ps.gz
>
> D'après " Concrete Mathematics" de Graham, Knuth et Patashnik
> (Addison-Wesley) , livre que je recommande par ailleurs
> inconditionnellement
> (en dépit de son prix), ce serait dû à Lord Rayleigh (1877). Une démo
> figure
> dans le bouquin, mais je vois que tu as déjà eu des réponses. La réciproque
> est vraie:[/color]

Histoire de donner un rayon de soleil dans ces mathématiques
bien sérieuses, une application ludique des suites de Beatty.

On considère la variante du jeu de Nim suivante :
soit deux tas de X et Y allumettes.
Chaque joueur à tour de rôle prend autant d'allumettes qu'il
veut dans un seul tas, ou une même quantité dans les deux tas.
Le gagnant est celui qui prend la (les) dernières allumettes.

La stratégie gagnante est de donner à l'adversaire des tas de
{x, y} = {partent[k*phi], partent[k*phi^2]}
avec phi le nombre d'or.
Comme 1/phi + 1/phi^2 = 1, ces nombres forment une partition
(ou suite) de Beatty et recouvrent donc N.
C'est à dire que tous les nombres entiers apparaissent une fois
et une seule dans la liste des {x, y}.

Trouver à partir d'une position donnée (a,b) le (x,y) gagnant :
le plus petit de (a,b) est forcément dans l'une des suites [n*phi]
ou [n*phi^2], appelons le a.

1) s'il est dans la suite [n*phi^2], l'autre, plus grand,
est b > [n*phi]
et donc retirer b - [n*phi] du plus grand.

2) s'il est dans la suite [n*phi] deux cas se présentent alors :
2a) le plus grand est > [n*phi^2], retirer b - [n*phi^2] du
plus grand
2b) sinon il faut retirer une même quantité aux deux tas.

Dans ce dernier cas on utilise une autre propriété des suites
[n*phi], [n*phi^2] qui est :
[n*phi^2] - [n*phi] = n = y - x = b - a (on a retiré la même
quantité à a et b pour obtenir x et y).
exemple (14, 19), b - a = 5, [5*phi] = 8, [5*phi^2] = 13
et donc retirer 6 aux deux tas.

Ceci est toujours possible si {a,b} n'est pas déja
{[n*phi], [n*phi^2]}.

Bon amusement.

--
philippe
(chephip à free point fr)

[Anonyme]

On 2004-10-27, Frederic wrote:
> On 2004-10-27, Iulius wrote:[color=green]
>> Bonjour,
>>
>> Un petit énoncé simple, mais je ne sais par où partir...
>>
>> On se donne deux réels strictement positifs a et b et l'on pose
>> A={partent(n*a), n>0} et B={partent(n*b), n>0}.
>> On demande une condition nécessaire et suffisante très simple
>> portant sur a et b pour que A et B forment une partition de N*.
>>
>> Auriez-vous une indication ?
>> D'avance merci.
>
> Ouh, c'est un classique. Un premier indice : au pifomêtre, la « densité »
> des partent(n*a) dans N (ça y en a pas être très formalisé, m'enfin avec
> les mains, ça se comprend) est 1/a, et celle des partent(n*b) est 1/b.
> Il serait donc de bon ton que 1/a + 1/b = 1. Dans ce sens, ce n'est pas
> trop difficile à prouver (i.e. si {A, B} partitionne N*, alors
> 1/a+1/b=1). Par contre, la réciproque est un peu plus délicate.[/color]

Il faut d'ailleurs préciser : la CNS n'est pas « 1/a + 1/b = 1 »,
mais « 1/a + 1/b = 1 et a, b irrationnels ». En effet, si a (et donc
b) est rationnel, on écrit a = p/q, p et q premiers entre eux, puis
1/b = 1 - q/p = (p-q)/p donc b = p/(p-q). Donc maintenant,
pq = q^2 (p/q) est dans A, et pq = q(p-q) p/(p-q) est dans B. Ce qui
est une contradiction.

--
Frédéric