Due esercizi di combinatoria
Si determini il numero di regioni in cui una superficie sferica è suddivisa da n cerchi massimi tale che nessun punto appartenga a tre di essi.
Cosa si intende per "massimi"?
Sia dato un rettangolo m × n quadratini unitari. Quanti quadratini sono attraversati da una diagonale del rettangolo?
Grazie
Cosa si intende per "massimi"?
Sia dato un rettangolo m × n quadratini unitari. Quanti quadratini sono attraversati da una diagonale del rettangolo?
Grazie
Risposte
"RuCoLa":
Si determini il numero di regioni in cui una superficie sferica è suddivisa da n cerchi massimi tale che nessun punto appartenga a tre di essi.
Cosa si intende per "massimi"?
Si intende cerchi di raggio massimo, che sono quelli ottenibili tra l'intersezione della superficie sferica con un piano che passa per il centro della sfera. Al esempio i meridiani sono cerchi massimi, dei paralleli solo l'equatore è un cerchio massimo.
Nella geometria sferica, la distanza tra due punti è calcolata sull'arco di cerchio massimo che è la distanza minima tra i due punti.
Per il secondo:
se $m=n$ i quadrati tagliati dalla diagonale sotto esattamente $m$(o $n$ essendo uguali).
se $mnen$ io ho ragionato così:
Prendo un rettangolo lungo $m$ e alto $n$ e tiro la diagonale. Noto che si forma 'un percorso'. Il percorso va esattamente da una punta all'altra del rettangolo, dunque per compierlo dobbiamo fare $m+n-2$ spostamenti($m-1$ in orizzontale e $n-1$ in verticale). Dunque questo è il percorso che crea la diagonale, soltanto che dobbiamo aggiungere un quadratino poiché il primo non viene contato(infatti contiamo gli spostamenti. Ad esempio dal primo al secondo c'è uno spostamento). Oppure puoi pensare di compiere uno spostamento in più, insomma, è molto libero come problema.
La risposta dovrebbe essere $m+n-1$
se $m=n$ i quadrati tagliati dalla diagonale sotto esattamente $m$(o $n$ essendo uguali).
se $mnen$ io ho ragionato così:
Prendo un rettangolo lungo $m$ e alto $n$ e tiro la diagonale. Noto che si forma 'un percorso'. Il percorso va esattamente da una punta all'altra del rettangolo, dunque per compierlo dobbiamo fare $m+n-2$ spostamenti($m-1$ in orizzontale e $n-1$ in verticale). Dunque questo è il percorso che crea la diagonale, soltanto che dobbiamo aggiungere un quadratino poiché il primo non viene contato(infatti contiamo gli spostamenti. Ad esempio dal primo al secondo c'è uno spostamento). Oppure puoi pensare di compiere uno spostamento in più, insomma, è molto libero come problema.
La risposta dovrebbe essere $m+n-1$
Per il secondo:
Costruiamo un sistema di assi cartesiano ausiliare con l'origine coincidente col vertice sinistro inferiore. Senza perdita di generalità sia $n>=m$ e sia $n$ la lunghezza della base e $m$ la lunghezza dell'altezza.
Per determinare il numero di quadrati attraversati dalla diagonale consideriamo che la biezione che si viene a instaurare con le intersezioni effettive tra la diagonale (di equazione $y=(m/n)x$ e le rette $x=1,2,3...n$ e $y=1,2,3...m$. È facile convicersi che questi due insiemi sono in corrispondenza biunivoca: dal vertice alla prima intersezione attraversiamo un quadratino, dalla prima alla seconda intersezione ne attraversiamo un altro e così proseguendo fino al vertice opposto. Dunque il problema si riduce a determinare il numero di intersezioni effettive.
In virtù della crescenza stretta della funzione diagonale, per arrivare da $P_1(0,0)$ a $P_2(n;m)$ la retta incrocerà le rette verticali esattamente $n$ volte e le rette orizzontali esattamente $m$ volte. A queste dobbiamo sottrarre il numero di intersezioni coincidenti con una retta orizzontale e verticale (in quanto nella somma bruta li contiamo due volte). Notando ovviamente che le rette orizzontali e verticali si intersecano in tutti i punti a coordinate intere con ascissa minore di $n$ e ordinata minore di $m$, basta calcolare quanti sono i punti in cui la funzione diagonale ha entrambi i parametri interi nell'intervallo su cui stiamo lavorando. Per comodità, porremmo la $x$ compresa tra $1$ e $n$ per determinare in quali valori della $x$ intera anche la $y$ è intera. (Questo passaggio è ammissibile in quanto le rette del reticolato del rettangolo si incontrano in TUTTI i punti a coordinate intere nella regione in cui stiamo lavorando, dunque tutte le intersezioni intere con le rette orizzontali e la diagonale corrispondono anche alle intersezio con la diagonale e le rette verticali.)
Dunque il problema si riduce a trovare il valore
$m+n-|A_(mnn\text{n})|$ dove $|A|$ è la cardinalità dell'insieme delle intersezioni comuni.
Primo caso: $m$ e $n$ sono coprimi.
Allora ilñ rapporto $(m/n)*x$ con $x$ appartenente a $[1,2,3,...n]$ sarà intero solo quando $x$ è multiplo di $n$, e poiché l'unico numero dell'insieme multiplo di $n$ è ovviamente $n$, ci sarà una sola intersezione a coordinate intere (ovviamente graficamente essa corrisponde al vertice opposto della diagonale). Dunque in questo caso la formula restituisce $m+n-1$
Secondo caso: $m$ divide $n$
Sia allora $k$ il numero intero $n/m$ (ricordiamo che $n>=m$). Dobbiamo quindi trovare i valori interi di $(1/k)*x$ con $x$ appartenente al solito intervallo di riferimento. $x$ deve essere quindi multiplo di $k$, ma ovviamente i multipli di $k$ minori di $n$ sono $n/k=m$, quindi i valori da escludere sono $m$ e la formula restituisce $m+n-m=n$
EDIT: avevo mancato il caso di $m$ e $n$ con primi in comune, che si dimostra facilmente allo stesso modo. La formula generale è comunque: $m+n-gcd(m,n)$. Probabilmente esiste una soluzione più elegante che fa uso solamente della combinatoria. Sarei curioso di leggerla!
Costruiamo un sistema di assi cartesiano ausiliare con l'origine coincidente col vertice sinistro inferiore. Senza perdita di generalità sia $n>=m$ e sia $n$ la lunghezza della base e $m$ la lunghezza dell'altezza.
Per determinare il numero di quadrati attraversati dalla diagonale consideriamo che la biezione che si viene a instaurare con le intersezioni effettive tra la diagonale (di equazione $y=(m/n)x$ e le rette $x=1,2,3...n$ e $y=1,2,3...m$. È facile convicersi che questi due insiemi sono in corrispondenza biunivoca: dal vertice alla prima intersezione attraversiamo un quadratino, dalla prima alla seconda intersezione ne attraversiamo un altro e così proseguendo fino al vertice opposto. Dunque il problema si riduce a determinare il numero di intersezioni effettive.
In virtù della crescenza stretta della funzione diagonale, per arrivare da $P_1(0,0)$ a $P_2(n;m)$ la retta incrocerà le rette verticali esattamente $n$ volte e le rette orizzontali esattamente $m$ volte. A queste dobbiamo sottrarre il numero di intersezioni coincidenti con una retta orizzontale e verticale (in quanto nella somma bruta li contiamo due volte). Notando ovviamente che le rette orizzontali e verticali si intersecano in tutti i punti a coordinate intere con ascissa minore di $n$ e ordinata minore di $m$, basta calcolare quanti sono i punti in cui la funzione diagonale ha entrambi i parametri interi nell'intervallo su cui stiamo lavorando. Per comodità, porremmo la $x$ compresa tra $1$ e $n$ per determinare in quali valori della $x$ intera anche la $y$ è intera. (Questo passaggio è ammissibile in quanto le rette del reticolato del rettangolo si incontrano in TUTTI i punti a coordinate intere nella regione in cui stiamo lavorando, dunque tutte le intersezioni intere con le rette orizzontali e la diagonale corrispondono anche alle intersezio con la diagonale e le rette verticali.)
Dunque il problema si riduce a trovare il valore
$m+n-|A_(mnn\text{n})|$ dove $|A|$ è la cardinalità dell'insieme delle intersezioni comuni.
Primo caso: $m$ e $n$ sono coprimi.
Allora ilñ rapporto $(m/n)*x$ con $x$ appartenente a $[1,2,3,...n]$ sarà intero solo quando $x$ è multiplo di $n$, e poiché l'unico numero dell'insieme multiplo di $n$ è ovviamente $n$, ci sarà una sola intersezione a coordinate intere (ovviamente graficamente essa corrisponde al vertice opposto della diagonale). Dunque in questo caso la formula restituisce $m+n-1$
Secondo caso: $m$ divide $n$
Sia allora $k$ il numero intero $n/m$ (ricordiamo che $n>=m$). Dobbiamo quindi trovare i valori interi di $(1/k)*x$ con $x$ appartenente al solito intervallo di riferimento. $x$ deve essere quindi multiplo di $k$, ma ovviamente i multipli di $k$ minori di $n$ sono $n/k=m$, quindi i valori da escludere sono $m$ e la formula restituisce $m+n-m=n$
EDIT: avevo mancato il caso di $m$ e $n$ con primi in comune, che si dimostra facilmente allo stesso modo. La formula generale è comunque: $m+n-gcd(m,n)$. Probabilmente esiste una soluzione più elegante che fa uso solamente della combinatoria. Sarei curioso di leggerla!
Grazie mille per la risposta!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo