OliForum Matematico

Ho passato circa mezz'ora sul problema dei piatti, e ne e' valsa la pena...

Infatti, a forza di apparecchiare, si dimostra in maniera puramente combinatorica un simpatico lemma di TdN, cioe':

sia $ A=\{ a_1,\dots ,a_n,\dots \} $ una successione e $ m $ un intero positivo tali che, per ogni n intero positivo:

$ \displaystyle\sum_{d|n} a_d=m^n $

Dimostrare che, per ogni n intero positivo:

$ n|a_n $

Buon lavoro.

mmm..si vede che a1=m e che per ogni p si ha a(p)=m^p-m e quindi p| a(p) ovviamente. con p e q primi diversi tra loro si ha a(pq)=m^pq +m - (m^p + m^q), anche qua ovvio modulo p e modulo q..
pero non riesco a trovare l'induzione che mi permette di arrivare alla tesi

Bellissimo questo problema!

Per ricollegarci ai piatti di Archimende, consideriamo il problema seguente: e' data una tavola circolare con $ n $ posti e si hanno piatti di $ m $ colori. Voglimo sapere quante sono le apparecchiature distinte, dove due apparecchiature sono identificate se esiste una rotazione che porta l'una nell'altra.

Indichiamo con $ x_{n,k} $ il numero di apparecchiature su $ n $ posti che vengono fissate da esattamente $ k $ rotazioni. Allora $ k|n $ e si ha $ x_{n,k}=x_{{n/k},1} $. Inoltre il numero di apparecchiature distinte senza considerare le identificazioni che vengono dalle rotazioni e' ovviamente $ m^n $, e questo ci da la formula

$ m^n=\sum_{k|n}\frac{n}{k}x_{n,k}=\sum_{k|n}\frac{n}{k}x_{{n/k},1}= $
$ =\sum_{d|n}dx_{d,1} $

Allora, se poniamo $ a_n=n\, x_{n,1} $, si ha $ n|a_n $ e la successione $ \{a_n\} $ soddisfa la relazione
$ \sum_{d|n}a_d=m^n $
per ogni $ n $. Poiche' questa relazione determina univocamente gli $ a_n $, segue la tesi.