[L03/04] Boring numbers (ma anche no)

[Salvador]

Definiamo numeri noiosi il 2 e tutti i numeri della forma $3^a5^b$, dove $a$ e $b$ sono due interi non negativi. Dimostrare che ogni intero positivo può essere scritto come somma di uno o più numeri noiosi distinti.
(Consiglio: secondo voi che livello è?)

[Vinciii]

Qualche hint?

[Lasker]

Testo nascosto:

Se tu dovessi trovare materialmente una scomposizione assicurandoti di avere numeri tutti diversi, come faresti (in modo "greedy")? Poi visto che si parla di una proprietà dei naturali, quale sarebbe una buona idea per formalizzare questo procedimento intuitivo?

Questa idea a formalizzarla ci dovresti perdere un po', ho dovuto fare un po' di conticini per verificare che funzionava davvero (non arrenderti perché tornano). Ad occhio il livello che ha messo Salvador è buono.

[Vinciii]

Testo nascosto:

Avevo intuito che si facesse con l'induzione ed ho provato ad attaccarlo, ma mi sono bloccato dopo. :\

[Gerald Lambeau]

L'induzione diciamo che non è indispensabile, o almeno non c'è bisogno che sia formalissima: nella cosa greedy che dice Lasker ci basta dire che (attenzione, spoiler)

Testo nascosto:

il massimo numero noioso minore o uguale di un numero intero positivo dato è tale che il suo doppio dev'esserne strettamente maggiore; questa cosa si fa per assurdo: se così non fosse, ci sarebbe un numero maggiore o uguale sia di un numero noioso che del suo doppio e tale che non ci sono altri numeri noiosi in mezzo. Ma si può dimostrare che per ogni numero noioso $n$ esiste un numero noioso $n'$ tale che $n<n' \le 2n$; per farlo in realtà ci bastano (lascio a voi il perché) i casi $n=1, 3, 5$ (tra parentesi, $n=1$ è ovviamente l'unico caso dove può essere che $n'=2n$).

[Salvador]

Stesso tipo di idee di Gerald e Lasker

Testo nascosto:

Parto dal presupposto che se $x$ è un numero noioso e so che tutti i numeri tra $1$ e $x-1$ si possono scrivere secondo la tesi allora quelli tra $x+1$ e $2x-1$ si possono ottenere semplicemente aggiungendo $x$ (che ovviamente è diverso da qualunque altro numero presente perché maggiore); banalmente si ha poi che se $x=3^n$ allora $y=5 * 3^{n-1}$ è tale che $x<y<2x$, e se $x=5 * 3^{n-1}$ allora $y=3^{n+1}$ è tale che $x<y<2x$, dunque prendendo $x$ come nel primo caso posso scrivere sommando $x$ fino a $y-1$, poi $y$ lo scrivo da solo e sommo $y$ a quelli da $y+1$ a $3x-1$, poi faccio lo stesso con $3x$ fino a $3y-1$ e così via.

Per quanto riguarda invece la domanda sul livello, che ne pensate?