OliForum Matematico

Dato $ ~ n \in \mathbb{N} $, determinare $ ~ |\{km : n^2 \le k \le m \le (n+1)^2 \}| $.

Mi scuso per l'enunciazione troppo simbolica, però il problema (dato alle nazionali polacche 2007) è proprio carino!

Up!

Suvvia gente!

Sapete tanto che edriv ha la mania di postare miliardi di esercizi che si fanno tutti allo stesso modo.

Con un'idea sola potete risolvere anche quest'altro problema!

Sì vabeh quel povero problema l'hai martoriato tu coi tuoi cannoni... mi pare che l'idea sia degna di essere presente in questo forum, no?

Molto probabilmente ho frainteso il problema...
Ma se quello che chiedi è il numero di coppie comprese tra $ n^2 $ e $ (n+1)^2 $, la risposta non dovrebbe essere banalmente $ (n+1)(2n+3) $?

No, non chiedo quante sono le coppie, ma quanti sono i prodotti!
Ad esempio se capitano (3,4), (4,3) e (2,6), queste le devo contare una sola volta.

Ok!
Allora dovrebbe essere $ (x+2)(2x+1) $.
Non ne sono sicuro, perciò, prima di proseguire a scrivere demenzialità, ricontrollerò il tutto...

My 2 cent: concordo con il risultato di Feddy, e butto lì una dimostrazione ben poco formale.

Mi sembra abbastanza evidente che il problema vero è quello esposto da edriv nel titolo: quante coppie troviamo che diano lo stesso prodotto e stiano lì dentro?

Per rispondere costruisco una tabella quadrata con tutti i possibili prodotti. Ne prendo solo metà sia perchè tanto è simmetrica sia perchè per il problema mi serve solo una metà. Considero le "semidiagonali" (le "semidiagonali" sono oggettini fatti $ x+y=k, x \geq y $ dove x e y sono le coordinate della casella e k è un intero fissato)

EDIT: avevo fatto un po' di casino con x e y chiamandole un po' così e un po' a e b...

I fatti da dimostrare (conti) sono questi: lungo le semidiagonali c'è ordinamento stretto, tra una semidiagonale e l'altra c'è ordinamento "largo" (nel senso che il massimo di una può essere il minimo della successiva).

Questo però succede solo se (viene una simpatica equazione di secondo grado) $ k=2(n^2+n) $, quindi esttamente una volta. In definitiva i prodotti possibili sono tutti tranne 1, ossia il risultato di FeddyStra.

Ciao!

Letto, testato, controllato: funziona benissimo!

L'altra soluzione (che secondo me non può venire in mente senza aver già visto il lemma) si basa appunto sul lemma:
Se a,b,c,d sono interi positivi tali che ab=cd e (a,b,c,d) = 1; allora esistono e,f,g,h interi positivi, a due a due coprimi, tali che a = ef,b=gh, c=fg, d=eh.
Dimostrazione: prendiamo
$ ~ e = \frac{a}{(a,c)} = \frac{d}{(d,b)} $
$ ~ g = \frac{c}{(a,c)} = \frac{b}{(d,b)} $
$ ~ f = (a,c) $
$ ~ g=(b,d) $
Verifichiamo che funzionano e che le uguaglianze scritte sopra son vere (a voi).

E non ho voglia di scrivere altro che il lemma