156. Rappresentazioni in base - variazioni sul tema

[Gottinger95]

Definiamo una base \(B = ( (x_n), (y_n))\) una coppia ordinata di sequenze di interi positivi tale che:
1. Per ogni \(n\), esistono \(a_1, \ldots, a_k\) tali che \(0 \le a_i \leq y_i\) e che
\(\displaystyle \sum_{i=1}^k{a_ix_i} = n\).
2. La rappresentazione è unica, ossia non esiste nessun \(n\) tale che
\(\displaystyle \sum_{i=1}^{k_1}{a_ix_i} = n = \sum_{i=1}^{k_2}{b_ix_i}\)
per \((a_1, \ldots, a_{k_1}) \neq (b_1, \ldots, b_{k_2})\) e \(0 \le a_i, b_i \leq y_i\) per ogni \(i\).

(a) Determinare per quali sequenze \((x_n)\) esiste una sequenza \((y_n)\) tale che \( ( (x_n), (y_n) )\) forma una base.
(b) Data una sequenza "buona" \((x_n)\) (quelle determinate al punto (a) ), determinare una sequenza \((y_n)\) (forse la sequenza) tale che \(( (x_n), (y_n) )\) forma una base.
(c) Sia \(B = ((x_n), (y_n))\) una base, e sia \(A = (a_1, \ldots, a_k) \) una \(k\)-upla di interi non negativi tali che \(\sum_{i=1}^k{a_ix_i} = m\). Dimostrare che, fissato \(m\) e con \(k\) variabile, la somma \(S(A) = a_1 + \ldots + a_k\) è minima se e solo se \(a_i \le y_i\) per ogni \(i\) (ossia se rispetta le condizioni della rappresentazione in base).

[Gottinger95]

Ma non lo fa nessuno? In fondo non è così complicato, è praticamente una generalizzazione del 155.!
..Forse non è molto stimolante?

[Triarii]

Mmm, forse ho una soluzione, solo che mi pare che il punto a sia molto simile al punto b, quindi ci sta abbia frainteso le richieste...

[Gottinger95]

No, effettivamente se hai seguito il mio stesso procedimento hai più meno fatto il punto (b) mentre facevi il punto (a), però le richieste sono diverse. Magari qualcuno trovava un procedimento per fare il punto (a) senza passare per il punto (b) ! Dai, mettila pure

[Triarii]

(Do per scontato che gli $x_n$ siano ordinati in maniera strettamente crescente)
Il numero $1$ deve essere rappresentabile. $1=a_1x_1$ da cui $x_1=1$ necessariamente. (per lo 0 non ci sono vincoli particolari: basta $a_1=0$)
Si nota che $y_1x_1+...y_kx_k$ è il massimo numero esprimibile con usando le $x$ fino a $x_k$. Necessariamente quindi questo numero deve essere pari a $x_{k+1}-1$. Infatti non può essere pari a $x_{k+1}$ perchè altrimenti verrebbe meno l'unicità, e è necessariamente il precedente perchè se così non fosse ci sarebbero numeri che non avrebbero rappresentazione.
Usando le $x$ fino a $x_k, ho (y_1+1)...(y_k+1)$ modi per rappresentare i numeri. Data l'unicità, ad ogni rappresentazione diversa corrisponde un numero diverso, quindi, visto che con $x_k$ posso arrivare a scrivere i numeri fino a $x_{k+1}-1$, vale $(y_1+1)...(y_k+1)+1=x_{k+1}$
Andiamo ora a dimostrare il punto c.
Prendo come ipotesi il fatto che $m$ sia scritto in base, e dimostro che $S(A)$ è minimo.
Cerco di costruire una rappresentazione non in base di $m$ aumentando qualche $a$ in modo che sia maggiore del rispettivo $y$, rompemdo così le regole della rappresentazione in base. Notiamo intanto che se per esempio diminuisco $a_i$, non posso "trasferire" questa quantità (e nemmeno quelle di tutti gli $x_j$ con $j<i$) a $a_{i+1}$, in quanto per le condizioni della base, $1\cdot x_{i+1}>y_ix_i$. Posso tuttavia fare il contrario, ossia passare parte della quantità $a_i$ ai a vari $a_{i-1}...a_1$. Tuttavia così facendo $S(A)$ aumenta poichè se $a_i$ diminuisce di $k\le y_i$ unità, già il solo a_{i-1} per ricevere una unità di $a_i$ aumenta di $x_i>1$ (infatti per quanto detto non posso far diminuire le unità di $a_1$ visto che questa quantità non può essere trasferita a $a_2$ e seguenti). Quindi ogni volta che trasferisco parte di $a_i$ a a con indice minore (l'unica mossa possibile) $S(A)$ aumenta. La rappresentazione in base ha quindi $S(A)$ minimo
Dimostriamo ora che se $S(A)$ è minimo, allora $m$ è rappresentato in base.
Se non fosse rappresentato in base, potrei diminuire $S(A)$ con un procedimento analogo a quello sopra citato. Ma questi è impossibile perchè per ipotesi abbiamo che $S(A)$ è minimo. Assurdo, quindi $m$ è rappresentato in base

[Gottinger95]

Il punto (c) va bene, ma per la parte prima: chi ti dice che gli \(y_i\) siano interi? Bisogna verificarlo, e il vincolo sugli \(x_i\) diventa molto più semplice (e quadra con le rappresentazioni in base a cui siamo abituati e a quella fattoriale). Per la seconda parte, non hai detto quanto dovrebbe valere ogni \(y_i\) in termini degli \(x_i\). Nonostante questo, il ragionamento è perfetto, ti manca solo una piccola parte!

[Triarii]

Definiamo una base $B=((x_n),(y_n))$ una coppia ordinata di sequenze di interi positivi tale che...

Gli $y_i$ lo hai detto te che sono interi
Per la seconda parte dunque, dovrebbe valere che $y_i=\frac {x_{i+1}-x_i} {x_i}$. Ci si arriva sempre con $x_k-1=y_1x_1+...+y_{k-1}x_{k-1}$ e con l'induzione.
Poi si osserva che deve valere che $x_i$ divide $x_{i+1}$ perchè $y_i$ è intero (O forse avrei dovuto fare il contrario, dimostrando così l'interezza di $y_i$ ma sfrutto il fatto perchè lo hai detto tu all'inizio )

[Triarii]

Dunque ?

[jordan]

All'inizio della staffetta si era posto il limite di una settimana per ogni problema.. Vai pure

[Triarii]

Ok