[L04] Pasqua coi Polacchi!

[bern-1-16-4-13]

Sia $n$ un numero dispari. Determinare il numero di vettori $(x_1,x_2,...,x_n)\in\mathbb{R}^n$ tali che
$$x_i\left(x_i+1\right)=x_{i+1}\left(x_{i+1}-1\right)\ \ \ \ \forall i\le n$$(ovviamente indici modulo $n$)

[Gerald Lambeau]

Guarda che l'indice di difficoltà non c'è mica qui!

[bern-1-16-4-13]

ahahha hai ragione, però non sarebbe male inserirlo anche qui! Penso sia piuttosto utile

[Troleito br00tal]

Non capisco bene il testo: cosa intendi con aggiungere $1$ a un vettore e moltiplicare tra loro vettori?

[Gerald Lambeau]

Penso che gli $x_i$ presenti nel testo siano i singoli elementi del vettore, cioè $(x_1, x_2, \dots, x_n)$ è inteso come tutto un vettore del quale poi i singoli elementi devono rispettare la condizione.

[bern-1-16-4-13]

sì esatto, ma non so nemmeno io perché ho voluto scrivere vettore invece di $n$-upla

[Gerald Lambeau]

Giusto per sapere se sono sulla strada giusta:

Testo nascosto:

per caso ogni $n$-upla contiene lo $0$?

Se sì allora mi manca solo la parte contosa del problema.

[Gerald Lambeau]

Dunque? XD

[bern-1-16-4-13]

sorry, non avevo visto che avevi scritto

Testo nascosto:

Sì, è vero

[Gerald Lambeau]

Purtroppo quel tipo di conti non sono il mio forte, ma per correttezza metto quello che ho trovato.

Testo nascosto:

Innanzitutto da $x_{i+1}^2-x_{i+1}-x_i^2-x_i=0$ ci ricaviamo $\displaystyle x_{i+1}=\frac{1 \pm (2x_i+1)}{2}$, quindi $x_{i+1}=-x_i \lor x_i+1$.
Per non confonderci fra un cambio di segno e un incremento di $1$ dobbiamo eliminare il caso in cui $-x=x+1$, cioè dobbiamo dimostrare che il vettore non contiene l'elemento $-\frac{1}{2}$. Se lo contenesse possiamo considerare il vettore raddoppiato, che sarebbe necessariamente di interi, dove da un elemento al successivo si cambia segno o si somma $2$. Notiamo che qualunque sia il passaggio modulo $4$ il vettore diventa $-1, 1, -1, 1, \dots$ e dato che dobbiamo iniziare con un $-1$ e finire con un $1$ il vettore avrebbe un numero pari di elementi, assurdo.
Ora che possiamo ben distinguere fra cambio di segno e incremento di $1$ procediamo a dimostrare per assurdo che il numero di cambi di segno effettuati fra $x_1$ e $x_n$ (il passaggio da $x_n$ a $x_1$ non lo contiamo) sia dispari a patto di non essere nel vettore nullo.
Se ci fossero solo cambi di segno allora avremmo $x_1=x_n=x$ e dovrebbe valere $x=-x$ cioè dovrebbe essere il vettore nullo, che effettivamente funziona sempre.
Supponiamo quindi che ci sia un $x_i$ tale che $x_{i+1}=x_i+1$, allora dato che ruotare tutti gli elementi ci riporta sempre in un vettore valido possiamo supporre WLOG che quell'elemento sia $x_n$, abbiamo dunque $x_1=x, x_n=x-1$.
Supponiamo per assurdo che il numero di cambi di segno sia pari, allora $x_n=x+k-h=x-1 \Rightarrow h=k+1$ dove $k$ è il numero di incrementi effettuati dopo un numero pari di cambi di segno e $h$ è il numero di incrementi effettuati dopo un numero dispari di cambi di segno. Allora il numero di elementi del vettore è $1 \, (quello \, iniziale)+numero \, passaggi$, dove il numero di passaggi è uguale al numero di cambi di segno più il numero di incrementi. Il numero di incrementi è $h+k=2k+1$ dispari, mentre il numero di cambi di segno è stato supposto pari, quindi il numero di passaggi è dispari e il numero totale di elementi del vettore è pari, assurdo! Dunque si ha un numero dispari di cambi di segno.
Dimostriamo di essere in un vettore di interi. Per quanto detto $x-1=-x+k-h$, dove stavolta $k$ è il numero di incrementi effettuati dopo un numero dispari di cambi di segno e $h$ è il numero di incrementi effettuati dopo un numero pari di cambi di segno. Ne ricaviamo che $2x=k-h+1$. Dato che il numero di passaggi è pari (numero elementi del vettore - 1, il primo) e il numero di cambi di segno è dispari è dispari anche il numero totale di incrementi, quindi lo è $k+h$ e di conseguenza anche $k-h$, quindi $2x=k-h+1$ è un intero pari e quindi $x$ è intero.
Ci manca solo da dimostrare che si ha sempre uno $0$. Se $x=0, 1$ è banale, resta quindi $x \ne 0, 1$. Notiamo che in questo caso $x-1$ ha lo stesso segno di $x$. Supponiamo di non raggiungere mai lo $0$: ciò significa che con gli incrementi non possiamo mai cambiare di segno, altrimenti ci dovremmo necessariamente passare (per andare dagli interi negativi agli interi positivi, mentre dagli interi positivi si resta sempre negli interi positivi), quindi il numero di volte in cui si cambia di segno è effettivamente uguale al numero di cambi di segno, che è dispari, e quindi il segno di $x_n$ è opposto al segno di $x_1$, ma abbiamo detto che questo non può essere, assurdo! Quindi si ha sempre almeno uno $0$.
Da qui non riesco a proseguire, si dimostra facilmente che la somma di tutti gli elementi del vettore è $0$ e quindi ci dev'essere un numero pari di numeri dispari e un numero dispari di numeri pari, ma anche con queste informazioni non trovo un modo semplice per contare il numero effettivo di vettori. Una soluzione fino a questo punto secondo te quanti punti prenderebbe?

EDIT 1: Inviato per sbaglio, va finita!
EDIT 2: ora è "completa"
EDIT 3: typo

[bern-1-16-4-13]

Ora che possiamo ben distinguere fra cambio di segno e incremento di $1$ procediamo a dimostrare per assurdo che il numero di cambi di segno effettuati fra $x_1$ e $x_n$ (il passaggio da $x_n$ a $x_1$ non lo contiamo) sia dispari a patto di non essere nel vettore nullo.

Questa cosa che dici è vera solo nel caso in cui $\color{red}{\text{da $x_n$ a $x_1$ ci sia un incremento}}$.
Tuttavia da quello che hai scritto dopo si vede che questa specificazione l'hai effettivamente considerata, infatti hai fatto tutto questo discorso (che potevi evitare se includevi nel tuo conteggio anche il passaggio da $x_n$ a $x_1$)

Se ci fossero solo cambi di segno allora avremmo $x_1=x_n=x$ e dovrebbe valere $x=-x$ cioè dovrebbe essere il vettore nullo, che effettivamente funziona sempre.
Supponiamo quindi che ci sia un $x_i$ tale che $x_{i+1}=x_i+1$, allora dato che ruotare tutti gli elementi ci riporta sempre in un vettore valida possiamo supporre WLOG che quell'elemento sia $x_n$, abbiamo dunque $x_1=x, x_n=x-1$.

per ridurti alla situazione $\color{red}{\text{rossa}}$.

dove stavolta $k$ è il numero di incrementi effettuati dopo un numero dispari di cambi di segno e $h$ è il numero di incrementi effettuati dopo un numero pari di cambi di segno.

Per definire una volta sola $h$ e $k$ ti sarebbe convenuto definirli in funzione del numero di cambi di segno che seguono, e non che precedono un incremento, ma questo non è un problema..


Il discorso finale non è utile per la dimostrazione che conosco (e non penso sia utile in generale).

Ti manca solo un passaggio che prevede un pizzico di combinatoria, che penso che varrebbe più o meno la metà della dimostrazione. Poi forse un mezzo punto ti potrebbe essere levato per la poca chiarezza nel punto di cui ti ho parlato all'inizio.
Quindi direi che ti potevano dare intorno ai 3 punti.

[Gerald Lambeau]

Ok, grazie dei chiarimenti! Lo so che è tutta combinatoria ora, ma proprio non ho idea di come procedere... ci penserò su.

[bern-1-16-4-13]

Di niente, tranquillo che è meno contoso di quello che tu possa immaginare

Quando vuoi eventuali hint chiedi pure (magari in privata, fai un po' te..)

[cip999]

Allora, non ho letto la "mezza soluzione meno un po'" di sopra, quindi parte delle cose che scriverò saranno già state dette.

Testo nascosto:

Risolvendo $x_i(x_i + 1) = x_{i + 1}(x_{i + 1} - 1)$ in $x_{i + 1}$ otteniamo $\displaystyle x_{i + 1} = \frac{1 \pm (2x_i + 1)}{2}$, quindi $x_{i + 1} = -x_i$ oppure $x_{i + 1} = x_i + 1$.
Ora ci conviene riformulare il problema in questo modo: scegliamo un numero $a$ (che sarebbe $x_1$) e facciamo $n$ mosse che consistono nel sostituire il numero corrente $t$ con (a) $-t$ oppure (b) $t + 1$, in modo che alla fine ci ritroviamo con $a$. In quanti modi possiamo farlo? (Due modi sono da considerarsi distinti se differiscono per il numero di partenza o per la sequenza di mosse)
Osserviamo che, se chiamiamo $p$ il numero di mosse (a) e $q$ il numero di mosse (b), il numero finale sarà $(-1)^pa + s$, dove $s$ è un intero che ha la stessa parità di $q$. Distinguiamo quindi due casi:

• Se $p$ è pari, si deve avere $a + s = a \implies s = 0$, il ché implica che anche $q$ è pari, assurdo perché $p + q = n$ è dispari.
• Se $p$ è dispari, si deve avere $-a + s = a \implies s = 2a$ e quindi $q$ pari. [O meglio, $q$ è necessariamente pari, quindi lo è anche $s$, quindi $a = \frac{s}{2}$ è intero]

Ora poniamo $p = 2k - 1$ e, per $2 \le i \le 2k$, definiamo $y_k$ come il numero di mosse (b) tra la $(i - 1)$-esima e la $i$-esima mossa (a); denotiamo inoltre con $y_1$ il numero di mosse (b) fatte prima della prima mossa (a). Non è difficile notare che valgono le seguenti:
(i) $y_1 + y_2 + \cdots + y_{2k} + 2k - 1 = p + q = n$
(ii) $y_1 - y_2 + y_3 - \cdots + y_{2k - 1} - y_{2k} = 2a$ è pari
Si vede chiaramente che esiste una bigezione tra le $(2k)$-uple $(y_1, \: \dots, \: y_{2k})$ (dove $k$ non è fissato) che soddisfano queste due e le cose che vogliamo contare. D'altra parte, la (i) implica la (ii), quindi ci basta contare le $(2k)$-uple che verificano (i) per ogni possibile $k$, che d'ora in poi saranno felici. Se chiamiamo $f(r)$ il numero di $(2r)$-uple felici, con $r$ stavolta fissato, sappiamo che $f(r)$ è il numero di modi di sommare a $n - 2r + 1$ con $2r$ addendi non negativi, cioè $\displaystyle f(r) = \binom{n}{2r - 1}$. In totale, le $(2k)$-uple felici sono dunque $$\sum_{r = 1}^{\frac{n + 1}{2}} f(r) = \sum_{r = 1}^{\frac{n + 1}{2}} \binom{n}{2r - 1} = \binom{n}{1} + \binom{n}{3} + \cdots + \binom{n}{n} = 2^{n - 1}$$

[bern-1-16-4-13]

Ok, mi sembra vada tutto bene (perdonami se non ho controllato minuziosamente ma comunque le idee ci sono tutte).

Giusto una scorciatoia per il conteggio finale. Una volta definita una sequenza di $n$ mosse ognuna scelta tra le due a disposizione, se $p$ è dispari esiste sempre ed è univocamente determinata la $x$ di partenza che permetta di chiudere il circuito. Le sequenze di mosse in totale sono $2^n$, quindi $2^{n-1}$ saranno le sequenze con $p$ dispari, quindi $2^{n-1}$ saranno tutte le possibili soluzioni. E fine