Ciau! Era un pezzo che non proponevo un problema, almeno così mi pare di ricordare.. Questa è una rielaborazione di un quesito di Oblomov che si trova in Matematica non Elementare. Ma questo particolare punto possiede una soluzione completamente elementare, so here it goes!
Poniamo un osservatore nell'origine di un piano cartesiano, ed immaginiamo che su ogni punto a coordinate intere (esclusa l'origine) sia appoggiata una colonna cilindrica di raggio $ r $, con $ 0<r< \frac 1 2 $. Dimostrare che solamente un numero finito di colonne è visibile all'osservatore, e che la massima distanza tra l'origine ed il centro di una colonna visibile è al più $ \displaystyle \sqrt{2{\left\lceil \frac 1 r \right\rceil }^2-6\left\lceil \frac 1 r \right\rceil+5} $.
Nota: con argomenti più sofisticati si può ridurre la stima precedente a $ \displaystyle\sqrt{r^2+\frac 1 {r^2}} $.
Il mare di colonne
Bonus question:
poniamo un osservatore nell'origine dello spazio $ n $-dimensionale ($ n\geq 3 $), ed in ogni punto a coordinate intere (esclusa l'origine) poniamo un'ipersfera di raggio $ r $, con $ 0<r<\frac12 $. Allora, l'osservatore può vedere solamente un numero finito di ipersfere, i cui centri distano dall'origine strettamente meno di $ \displaystyle \sqrt{n}\left( {\left\lceil \frac {\sqrt{n-1}} r \right\rceil}^{n-1}-2^{n-1}+1 \right) $.
poniamo un osservatore nell'origine dello spazio $ n $-dimensionale ($ n\geq 3 $), ed in ogni punto a coordinate intere (esclusa l'origine) poniamo un'ipersfera di raggio $ r $, con $ 0<r<\frac12 $. Allora, l'osservatore può vedere solamente un numero finito di ipersfere, i cui centri distano dall'origine strettamente meno di $ \displaystyle \sqrt{n}\left( {\left\lceil \frac {\sqrt{n-1}} r \right\rceil}^{n-1}-2^{n-1}+1 \right) $.
MindFlyer,ti ringrazio per esserti interessato al problema.
I risultati che proponi sono molto interessanti e ti chiederei di scrivere(molto dettagliatamente e scrivendo più passaggi possibile)come si dimostrano(e magari quale ragionamento ti ha fatto pervenire alla soluzione),ovviamente dopo che gli altri avranno o non avranno postato le loro(non sono problemi semplici).
Insomma prego tutti di scrivere i loro risultati su questo e sul mio topic,sempre in osservanza al principio di spiegare tutto.
E' un problema che mi sta molto a cuore...
Grazie.
Ciao!
I risultati che proponi sono molto interessanti e ti chiederei di scrivere(molto dettagliatamente e scrivendo più passaggi possibile)come si dimostrano(e magari quale ragionamento ti ha fatto pervenire alla soluzione),ovviamente dopo che gli altri avranno o non avranno postato le loro(non sono problemi semplici).
Insomma prego tutti di scrivere i loro risultati su questo e sul mio topic,sempre in osservanza al principio di spiegare tutto.
E' un problema che mi sta molto a cuore...
Grazie.
Ciao!
Why are numbers beautiful? It’s like asking why is Beethoven’s Ninth Symphony beautiful. If you don’t see why, someone can’t tell you. I know numbers are beautiful. If they aren’t beautiful, nothing is. - P. Erdös
Grazie a te per l'apprezzamento!
Pubblicherò con piacere la mia soluzione dopo che tutto il forum si sarà arreso. Molto più probabilmente vedremo una soluzione tale e quale alla mia, non è così complicata..
Come suggerimento, posso dire che come strumenti non richiede altro che un pigeonhole e un teorema di Pitagora, quindi non vi demoralizzate e provate!
Posso chiederti come mai ti sta così a cuore il problema?
Pubblicherò con piacere la mia soluzione dopo che tutto il forum si sarà arreso. Molto più probabilmente vedremo una soluzione tale e quale alla mia, non è così complicata..
Come suggerimento, posso dire che come strumenti non richiede altro che un pigeonhole e un teorema di Pitagora, quindi non vi demoralizzate e provate!
Posso chiederti come mai ti sta così a cuore il problema?
Uno perché é molto bello e due perché mi piace molto.
Certo non deve essere nemmeno molto semplice...
Ciao!
GioMott
Certo non deve essere nemmeno molto semplice...
Ciao!
GioMott
Why are numbers beautiful? It’s like asking why is Beethoven’s Ninth Symphony beautiful. If you don’t see why, someone can’t tell you. I know numbers are beautiful. If they aren’t beautiful, nothing is. - P. Erdös
Re: Il mare di colonne
Vediamo innanzitutto che se una colonna ha coordinate $ (a;b) $, con $ MCD(a; b)=d>1 $, l'osservatore non potrà vederla, perché sarà coperta da una colonna di coordinate $ (\frac{a}{d}; \frac{b}{d}) $.
Sia $ P $ il centro di una colonna di coordinate $ (k;h) $ con $ MCD(k;h)=1 $.
Dimostriamo che se $ r\geq\frac{1}{k} $, l'osservatore non potrà vederla.
Siano $ A_1, A_2, ... , A_k $ i punti di coordinate $ (1;0), (2;0), ... (k;0) $, e sia $ O $ il nostro punto d'osservazione. Sia poi $ P_i $ il punto in cui la perpendicolare all'asse x per $ A_i $ interseca $ OP $ (i, d'ora in avanti, va da 1 a k-1), e sia $ T_i $ il punto le cui coordinate sono la parte intera di quelle di $ P_i $.
Ora, è chiaro che i triangoli $ OA_1P_1, ... , OA_KP $ sono tutti simili e che $ A_iP_i=\frac{h\times i}{k} $; dunque $ T_iP_i=\frac{t}{k} $, dove t è un intero minore di k.
Abbiamo quindi k-1 valori possibili per i $ T_iP_i $. Se ve ne fossero due uguali, però (diciamo $ T_aP_a $ e $ T_bP_b $), le rette $ T_aT_b $ e $ OP $ sarebbero parallele. Ma allora $ T_aT_b $ sarebbe l'ipotenusa di un triangolo rettangolo con lati paralleli agli assi e minori di h e k, con vertici a coordinate intere, simile ad $ OA_kP $: quindi h e k non sarebbero primi fra loro, contraddizione.
Ne deduciamo che i $ T_iP_i $ assumono tutti i diversi k-1 valori possibili. Tra di essi vi saranno dunque $ \frac{1}{k} $ e $ \frac{k-1}{k} $.
Questo significa che abbiamo due colonne la cui distanza dalla retta $ OP $ è minore di $ \frac{1}{k} $, cioè minore di r, e perciò queste due colonne c'impediranno di vedere la colonna in $ (h;k) $.
Tutto ciò significa che, dato r, noi non vedremo sicuramente le colonne che hanno una coordinata maggiore di $ \lceil\frac{1}{r}\rceil $. (L'ascissa come nella dimostrazione, o anche l'ordinata, per simmetria.)
Dunque la colonna più lontana che vediamo avrà coordinate al più uguali a $ \lceil\frac{1}{r}\rceil-1 $; ordinata e ascissa saranno distinte (altrimenti la colonna è coperta dalla $ (1;1) $), e dunque l'altra coordinata sarà $ \lceil\frac{1}{r}\rceil-2 $.
Con il teorema di Pitagora otteniamo facilmente che la distanza fra $ O $ e la nostra colonna è esattamente quella espressa nella formula data:
$ \displaystyle \sqrt{2{\left\lceil \frac 1 r \right\rceil }^2-6\left\lceil \frac 1 r \right\rceil+5} $
Sia $ P $ il centro di una colonna di coordinate $ (k;h) $ con $ MCD(k;h)=1 $.
Dimostriamo che se $ r\geq\frac{1}{k} $, l'osservatore non potrà vederla.
Siano $ A_1, A_2, ... , A_k $ i punti di coordinate $ (1;0), (2;0), ... (k;0) $, e sia $ O $ il nostro punto d'osservazione. Sia poi $ P_i $ il punto in cui la perpendicolare all'asse x per $ A_i $ interseca $ OP $ (i, d'ora in avanti, va da 1 a k-1), e sia $ T_i $ il punto le cui coordinate sono la parte intera di quelle di $ P_i $.
Ora, è chiaro che i triangoli $ OA_1P_1, ... , OA_KP $ sono tutti simili e che $ A_iP_i=\frac{h\times i}{k} $; dunque $ T_iP_i=\frac{t}{k} $, dove t è un intero minore di k.
Abbiamo quindi k-1 valori possibili per i $ T_iP_i $. Se ve ne fossero due uguali, però (diciamo $ T_aP_a $ e $ T_bP_b $), le rette $ T_aT_b $ e $ OP $ sarebbero parallele. Ma allora $ T_aT_b $ sarebbe l'ipotenusa di un triangolo rettangolo con lati paralleli agli assi e minori di h e k, con vertici a coordinate intere, simile ad $ OA_kP $: quindi h e k non sarebbero primi fra loro, contraddizione.
Ne deduciamo che i $ T_iP_i $ assumono tutti i diversi k-1 valori possibili. Tra di essi vi saranno dunque $ \frac{1}{k} $ e $ \frac{k-1}{k} $.
Questo significa che abbiamo due colonne la cui distanza dalla retta $ OP $ è minore di $ \frac{1}{k} $, cioè minore di r, e perciò queste due colonne c'impediranno di vedere la colonna in $ (h;k) $.
Tutto ciò significa che, dato r, noi non vedremo sicuramente le colonne che hanno una coordinata maggiore di $ \lceil\frac{1}{r}\rceil $. (L'ascissa come nella dimostrazione, o anche l'ordinata, per simmetria.)
Dunque la colonna più lontana che vediamo avrà coordinate al più uguali a $ \lceil\frac{1}{r}\rceil-1 $; ordinata e ascissa saranno distinte (altrimenti la colonna è coperta dalla $ (1;1) $), e dunque l'altra coordinata sarà $ \lceil\frac{1}{r}\rceil-2 $.
Con il teorema di Pitagora otteniamo facilmente che la distanza fra $ O $ e la nostra colonna è esattamente quella espressa nella formula data:
$ \displaystyle \sqrt{2{\left\lceil \frac 1 r \right\rceil }^2-6\left\lceil \frac 1 r \right\rceil+5} $
Ok, la dimostrazione di phi è sostanzialmente giusta (anche se manca qualche puntualizzazione su alcuni casi particolari, sebbene un 7 a Cesenatico non gliel'avrebbe negato nessuno...). Quindi complimenti a phi!
Per completezza scrivo la mia soluzione, che usa un approccio leggermentissimamente diverso, e si estende facilmente al caso generale in dimensione n (phi, non so se la tua si generalizzi banalmente, dacci un'occhiata).
Lemma:
Dato $ \alpha \in \mathbb{R} $, e detta $ \{x\} $ la parte frazionaria di $ x $, allora tra i $ k-1 $ numeri $ \{\alpha\} $, $ \{2\alpha\} $, ..., $ \{(k-1)\alpha\} $ ve n'è almeno uno non compreso tra $ \frac 1 k $ e $ 1-\frac 1 k $.
Dimostrazione:
Partizioniamo l'intervallo $ [0,1] $ in $ k $ intervalli uguali, e supponiamo per assurdo che nessuno dei $ k-1 $ numeri dati cada nel primo o nell'ultimo. Allora per il principio dei cassetti ve ne saranno due (che chiamiamo $ \{a\alpha\} $ e $ \{b\alpha\} $, con $ 1\leq a < b \leq k-1 $) che cadono in uno stesso intervallo tra i rimanenti $ k-2 $. Ne segue che $ \frac 1 k \geq\{b\alpha\}-\{a\alpha\}=\{(b-a)\alpha\} $. Ma poiché $ 1\leq b-a \leq k-2 $, questo significa che un numero tra quelli dati cade nel primo intervallo, assurdo. Il lemma è così dimostrato.
Tornando al problema, poniamo $ k=\lceil 1/r \rceil $, e $ r'=1/k $. Poiché ovviamente $ k\geq 1/r $, allora $ r'\leq r $. Si consideri una retta $ y=\alpha x $ per l'origine, e le parti frazionarie delle ordinate delle sue intersezioni con le rette della forma $ x=n $. Per il lemma precedente, una delle prime $ k-1 $ intersezioni disterà al più $ r' $ dal centro di una colonna, e quindi a maggior ragione la retta intersecherà tale colonna.
Ne segue che ogni colonna la cui ascissa vale almeno $ k $ sarà invisibile dall'osservatore. Per simmetria, vale lo stesso discorso con le ordinate, e con le coordinate negative. Quindi i centri delle colonne visibili sono compresi nel quadrato centrato nell'origine e con lati di lunghezza $ 2(k-1) $, le più lontane delle quali sono quelle nei vertici. Ma poiché queste sono certamente invisibili per $ k>2 $ (e siccome $ r<1/2 $, questo vale sempre), allora le colonne più lontane potenzialmente visibili sono quelle immediatamente adiacenti, ovvero quella di coordinate $ \left(k-1,k-2\right) $ e simmetriche. Usando Pitagora per calcolare la distanza centro-origine, si perviene alla formula data dal testo.
Per risolvere la bonus question in dimensione n, basta generalizzare il lemma. Ovvero, al posto del segmento $ [0,1] $ basta considerare un ipercubo di dimensione n-1 e suddividerlo in $ k^{n-1} $ ipercubetti, applicando il pigeonhole per dimostrare che prima o poi vi è un'intersezione con uno degli ipercubetti ai vertici.
Per completezza scrivo la mia soluzione, che usa un approccio leggermentissimamente diverso, e si estende facilmente al caso generale in dimensione n (phi, non so se la tua si generalizzi banalmente, dacci un'occhiata).
Lemma:
Dato $ \alpha \in \mathbb{R} $, e detta $ \{x\} $ la parte frazionaria di $ x $, allora tra i $ k-1 $ numeri $ \{\alpha\} $, $ \{2\alpha\} $, ..., $ \{(k-1)\alpha\} $ ve n'è almeno uno non compreso tra $ \frac 1 k $ e $ 1-\frac 1 k $.
Dimostrazione:
Partizioniamo l'intervallo $ [0,1] $ in $ k $ intervalli uguali, e supponiamo per assurdo che nessuno dei $ k-1 $ numeri dati cada nel primo o nell'ultimo. Allora per il principio dei cassetti ve ne saranno due (che chiamiamo $ \{a\alpha\} $ e $ \{b\alpha\} $, con $ 1\leq a < b \leq k-1 $) che cadono in uno stesso intervallo tra i rimanenti $ k-2 $. Ne segue che $ \frac 1 k \geq\{b\alpha\}-\{a\alpha\}=\{(b-a)\alpha\} $. Ma poiché $ 1\leq b-a \leq k-2 $, questo significa che un numero tra quelli dati cade nel primo intervallo, assurdo. Il lemma è così dimostrato.
Tornando al problema, poniamo $ k=\lceil 1/r \rceil $, e $ r'=1/k $. Poiché ovviamente $ k\geq 1/r $, allora $ r'\leq r $. Si consideri una retta $ y=\alpha x $ per l'origine, e le parti frazionarie delle ordinate delle sue intersezioni con le rette della forma $ x=n $. Per il lemma precedente, una delle prime $ k-1 $ intersezioni disterà al più $ r' $ dal centro di una colonna, e quindi a maggior ragione la retta intersecherà tale colonna.
Ne segue che ogni colonna la cui ascissa vale almeno $ k $ sarà invisibile dall'osservatore. Per simmetria, vale lo stesso discorso con le ordinate, e con le coordinate negative. Quindi i centri delle colonne visibili sono compresi nel quadrato centrato nell'origine e con lati di lunghezza $ 2(k-1) $, le più lontane delle quali sono quelle nei vertici. Ma poiché queste sono certamente invisibili per $ k>2 $ (e siccome $ r<1/2 $, questo vale sempre), allora le colonne più lontane potenzialmente visibili sono quelle immediatamente adiacenti, ovvero quella di coordinate $ \left(k-1,k-2\right) $ e simmetriche. Usando Pitagora per calcolare la distanza centro-origine, si perviene alla formula data dal testo.
Per risolvere la bonus question in dimensione n, basta generalizzare il lemma. Ovvero, al posto del segmento $ [0,1] $ basta considerare un ipercubo di dimensione n-1 e suddividerlo in $ k^{n-1} $ ipercubetti, applicando il pigeonhole per dimostrare che prima o poi vi è un'intersezione con uno degli ipercubetti ai vertici.
Per dimostrare la stima $ \displaystyle\sqrt{r^2+\frac 1 {r^2}} $, si può ricorrere al Teorema del corpo convesso di Minkowski.
Consideriamo una retta $ s $per l'origine, ed il rettangolo di lati $ 2r $ e $ \frac 2 r $ centrato nell'origine, il cui lato lungo $ \frac 2 r $ è parallelo a $ s $. Siccome il rettangolo è convesso, ha area 4, ed è simmetrico rispetto all'origine, per il Teorema di Minkowski esso contiene 2 punti A e A' a coordinate intere simmetrici rispetto all'origine. Poiché $ s $ dista al più $ r $ da ogni punto del rettangolo, in particolare intersecherà le colonne centrate in A e A'. Così, al variare di $ s $, la colonna con intersezione più lontana avrà centro al più in un vertice del rettangolo corrispondente, ovvero a distanza $ \displaystyle\sqrt{r^2+\frac 1 {r^2}} $ dall'osservatore. Poiché le colonne distanti al più $ \displaystyle\sqrt{r^2+\frac 1 {r^2}} $ sono in numero finito, a maggior ragione le colonne visibili saranno in numero finito.
Consideriamo una retta $ s $per l'origine, ed il rettangolo di lati $ 2r $ e $ \frac 2 r $ centrato nell'origine, il cui lato lungo $ \frac 2 r $ è parallelo a $ s $. Siccome il rettangolo è convesso, ha area 4, ed è simmetrico rispetto all'origine, per il Teorema di Minkowski esso contiene 2 punti A e A' a coordinate intere simmetrici rispetto all'origine. Poiché $ s $ dista al più $ r $ da ogni punto del rettangolo, in particolare intersecherà le colonne centrate in A e A'. Così, al variare di $ s $, la colonna con intersezione più lontana avrà centro al più in un vertice del rettangolo corrispondente, ovvero a distanza $ \displaystyle\sqrt{r^2+\frac 1 {r^2}} $ dall'osservatore. Poiché le colonne distanti al più $ \displaystyle\sqrt{r^2+\frac 1 {r^2}} $ sono in numero finito, a maggior ragione le colonne visibili saranno in numero finito.