[L04] Pasqua coi Polacchi!
-
- Messaggi: 78
- Iscritto il: 23 mag 2015, 18:27
[L04] Pasqua coi Polacchi!
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$)
$$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
- Messaggi: 335
- Iscritto il: 17 mag 2015, 13:32
- Località: provincia di Lucca
Re: [L04] Pasqua coi Polacchi!
Guarda che l'indice di difficoltà non c'è mica qui!
"If only I could be so grossly incandescent!"
-
- Messaggi: 78
- Iscritto il: 23 mag 2015, 18:27
Re: [L04] Pasqua coi Polacchi!
ahahha hai ragione, però non sarebbe male inserirlo anche qui! Penso sia piuttosto utile
- Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
Re: [L04] Pasqua coi Polacchi!
Non capisco bene il testo: cosa intendi con aggiungere $1$ a un vettore e moltiplicare tra loro vettori?
- Gerald Lambeau
- Messaggi: 335
- Iscritto il: 17 mag 2015, 13:32
- Località: provincia di Lucca
Re: [L04] Pasqua coi Polacchi!
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.
"If only I could be so grossly incandescent!"
-
- Messaggi: 78
- Iscritto il: 23 mag 2015, 18:27
Re: [L04] Pasqua coi Polacchi!
sì esatto, ma non so nemmeno io perché ho voluto scrivere vettore invece di $n$-upla
- Gerald Lambeau
- Messaggi: 335
- Iscritto il: 17 mag 2015, 13:32
- Località: provincia di Lucca
Re: [L04] Pasqua coi Polacchi!
Giusto per sapere se sono sulla strada giusta:
Se sì allora mi manca solo la parte contosa del problema.
Testo nascosto:
"If only I could be so grossly incandescent!"
- Gerald Lambeau
- Messaggi: 335
- Iscritto il: 17 mag 2015, 13:32
- Località: provincia di Lucca
-
- Messaggi: 78
- Iscritto il: 23 mag 2015, 18:27
Re: [L04] Pasqua coi Polacchi!
sorry, non avevo visto che avevi scritto
Testo nascosto:
- Gerald Lambeau
- Messaggi: 335
- Iscritto il: 17 mag 2015, 13:32
- Località: provincia di Lucca
Re: [L04] Pasqua coi Polacchi!
Purtroppo quel tipo di conti non sono il mio forte, ma per correttezza metto quello che ho trovato.
EDIT 1: Inviato per sbaglio, va finita!
EDIT 2: ora è "completa"
EDIT 3: typo
Testo nascosto:
EDIT 2: ora è "completa"
EDIT 3: typo
Ultima modifica di Gerald Lambeau il 26 mar 2016, 19:13, modificato 2 volte in totale.
"If only I could be so grossly incandescent!"
-
- Messaggi: 78
- Iscritto il: 23 mag 2015, 18:27
Re: [L04] Pasqua coi Polacchi!
Questa cosa che dici è vera solo nel caso in cui $\color{red}{\text{da $x_n$ a $x_1$ ci sia un incremento}}$.Gerald Lambeau ha scritto: 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.
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$)
per ridurti alla situazione $\color{red}{\text{rossa}}$.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 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..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.
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
- Messaggi: 335
- Iscritto il: 17 mag 2015, 13:32
- Località: provincia di Lucca
Re: [L04] Pasqua coi Polacchi!
Ok, grazie dei chiarimenti! Lo so che è tutta combinatoria ora, ma proprio non ho idea di come procedere... ci penserò su.
"If only I could be so grossly incandescent!"
-
- Messaggi: 78
- Iscritto il: 23 mag 2015, 18:27
Re: [L04] Pasqua coi Polacchi!
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..)
Quando vuoi eventuali hint chiedi pure (magari in privata, fai un po' te..)
Re: [L04] Pasqua coi Polacchi!
Allora, non ho letto la "mezza soluzione meno un po'" di sopra, quindi parte delle cose che scriverò saranno già state dette.
Testo nascosto:
-
- Messaggi: 78
- Iscritto il: 23 mag 2015, 18:27
Re: [L04] Pasqua coi Polacchi!
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
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