Questa proprietà assurda è stata scoperta da un geologo ed è di dimostrazione del tutto olimpica.
Sia $n$ un intero positivo e sia $0=\frac{p_0}{q_0}<\frac{p_1}{q_1}<...<\frac{p_k}{q_k}=1$ la successione di tutte le frazioni ridotte ai minimi termini con denominatore $\le n$. Si dimostri che $\frac{p_{i-1}+p_{i+1}}{q_{i-1}+q_{i+1}}=\frac{p_i}{q_i}$ per ogni $0<i<k$.
Sequenza di Farey
- Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
Re: Sequenza di Farey
Hint (no soluzione totale)
Piuttosto, problema bonus: trovare il valore di $k$ in funzione di $n$ (magari boh, hint: capire quante frazioni vengono "aggiunte" nel passaggio da $n$ a $n+1$).
Testo nascosto:
Testo nascosto:
Testo nascosto:
Testo nascosto:
Testo nascosto:
Testo nascosto:
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
Re: Sequenza di Farey
Oppure si potrebbe continuare dal secondo hint di Talete per via geometrica, assegnando a $\frac{p_i}{q_i}$ il punto nel piano che ha coordinate $(q_i,p_i)$.
Poi da pc magari posto tutta la dimostrazione
Poi da pc magari posto tutta la dimostrazione
Re: Sequenza di Farey
Testo nascosto:
Ultima modifica di Linda_ il 03 gen 2017, 10:48, modificato 1 volta in totale.
Re: Sequenza di Farey
Woo, bella la soluzione geometrica, Linda! Non ci avevo pensato
Qualcuno per il problema bonus? È una scemenza dimostrarlo, una volta trovato il valore...
Qualcuno per il problema bonus? È una scemenza dimostrarlo, una volta trovato il valore...
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
Re: Sequenza di Farey
Grazie
Per il bonus, $k=1+\sum_{i=2}^{n}{\phi(i)}$.
Infatti ad ogni passaggio da $n$ a $n+1$ vengono aggiunte $\phi(n+1)$ frazioni, cioè quelle con denominatore $n+1$ e numeratore minore di $n+1$ e coprimo col denominatore. Questo perché le altre con denominatore $n+1$ e numeratore non coprimo con $n+1$ appartenevano già alla successione di "ordine" minore perché se ridotte ai minimi termini hanno denominatore $<n+1$.
Poi per $n=1$ abbiamo $k=2$ perché le frazioni della successione sono $0/1$ e $1/1$, dunque le frazioni della successione fissato $n$ sono $2+\sum_{i=2}^{n}{\phi(i)}$, da cui
$$k=1+\sum_{i=2}^{n}{\phi(i)}$$
Edit: non mi ero accorta che partiva da $\frac{p_0}{q_0}$ e non da $\frac{p_1}{q_1}$, sistemato
Per il bonus, $k=1+\sum_{i=2}^{n}{\phi(i)}$.
Infatti ad ogni passaggio da $n$ a $n+1$ vengono aggiunte $\phi(n+1)$ frazioni, cioè quelle con denominatore $n+1$ e numeratore minore di $n+1$ e coprimo col denominatore. Questo perché le altre con denominatore $n+1$ e numeratore non coprimo con $n+1$ appartenevano già alla successione di "ordine" minore perché se ridotte ai minimi termini hanno denominatore $<n+1$.
Poi per $n=1$ abbiamo $k=2$ perché le frazioni della successione sono $0/1$ e $1/1$, dunque le frazioni della successione fissato $n$ sono $2+\sum_{i=2}^{n}{\phi(i)}$, da cui
$$k=1+\sum_{i=2}^{n}{\phi(i)}$$
Edit: non mi ero accorta che partiva da $\frac{p_0}{q_0}$ e non da $\frac{p_1}{q_1}$, sistemato