OliForum Matematico

Avete presente quei giochini in cui c'è un disegno geometrico e ti chiedono: "Quanti triangoli ci sono? Quanti quadrati?". Ecco, durante l'ora di filosofia mi sono messo a ragionare su questo problemino che mi sono posto:

Dato un rettangolo quadrettato di dimensioni $ a $ e $ b $ ($ a\le b $), quanti quadrati (di qualsiasi dimensione) si possono individuare nella quadrettatura?

C'è una formula chiusa abbastanza carina, e come bonus question (Teoria dei Numeri) dimostrare che quella formula è un intero per qualsiasi scelta di a e b.
Lasciatelo fare ai meno esperti, è facile facile

Ok risolto ;) Ma dato che l'ho trovato abbastanza facile lascio fare a qualcun altro ;)
Il problema è molto carino e vi propongo questa:
Bonus question
La formula nel caso a=b è identica ad un altra formula importante sapete spiegarlo???

La bonus question è molto interessante e ci sto tutt'ora ragionando anche io ;)
Per la question della teoria dei numeri... consiglio di andare a truccehtti senza l'uso delle congruenze xD viene più facile.

Più che una bella soluzione cercherò di scrivere come sono arrivato alla formula passo per passo.

Ragionamento iniziale: i quadrati più piccoli che si possono formare sono, ovviamente, quelli unitari; i più grandi saranno invece quelli di lato a. Dovrò quindi contare tutti i quadrati con i lati compresi tra 1 ed $ a $ (estremi inclusi!).

Conteggio quadrati: banalmente i quadrati unitari saranno $ a\cdot b $; noto inoltre che i quadrati di lato 2 sono esattamente 1 in meno per ogni colonna e per ogni riga, cioè in tutto $ (a-1)\cdot (b-1) $; stesso ragionamento applico per i quadrati di lato 3,4,..,$ a $ : si avranno cosi $ (a-2)\cdot (b-2) $ quadrati di lato 3...$ [a-(a-1)]\cdot [b-(a-1)] $ quadrati di lato $ a $. Ora non mi resta che sommare tutti i quadrati e avremo la nostra formula

Scrivo la formula: noto che probabilmente si potrebbe scrivere il tutto come una sommatoria e con alcuni semplici passaggi trovare la formula che cerchiamo, noto anche che purtroppo questo non lo so fare ( ) quindi cerchiamo un altro metodo. Riscrivendo la formula dal numero di quadrati di lato maggiore e sostituendo a $ [a-(a-1)] $ 1, a $ [a-(a-2)] $ 2 e cosi via, avremo:
$ 1\cdot (b-a+1) + 2\cdot (b-a+2) +...+a\cdot (b-a+a) $.
Resta comunque una sommatoria mentre noi dobbiamo avere una formula chiusa, cosa fare?
Provo a moltiplicare i vari fattori e poi li separo in maniera furba, vediamo che succede: $ [b+2b+3b+...+ab] - [a+2a+3a+...+a^2] + [1^2+2^2+3^2+...+a^2] $. Sono ancora 3 sommatorie ma queste sappiamo trasformarle in formule chiuse: $ \frac{ab(a+1)}{2} - \frac{a^2(a+1)}{2} + \frac{a(a+1)(2a+1)}{6} $ da cui trovo finalmente la formula cercata:
$ \frac{-a^3+3a^2b+3ab+a}{6} $.

Bonus question: se a=b i primi due termini della penultima sommatoria si annullano quindi non a caso la formula è uguale a quella per trovare la somma dei primi $ a $ quadrati.

P.S scritta cosi la soluzione fa veramente schifo, spero però serva a far capire come in alcuni casi si riescano a superare "ostacoli" dovuti alle scarse conoscenze.

Beh ora resto solo la domanda di TdN.
Dimostrare che $ \dfrac{-a^3+3a^2b+3ab+a}{6} $ è intero. Dunque dobbiamo dimostrare che $ 6|-a^3+3a^2b+3ab+a \Rightarrow 6|a(a+1)(3b-(a-1)) $.
Osservato che $ 6|a(a+1)(a-1) $ ($ a-1,a,a+1 $sono tre numeri consecutivi quindi c' almeno un multiplo di $ 2 $ e un multiplo di $ 3 $) si conclude $ 6|a(a+1)(3b-(a-1)) $

Giusto! E per ndp15 scrivo le sommatorie:
$ \displaystyle \sum_{i=0}^{a-1}(a-i)(b-i)=\sum_{i=0}^{a-1}(ab-(a+b)i+i^2)=a^2b-\frac{a(a-1)(a+b)}{2}+\frac{a(a-1)(2a-1)}{6}=\frac{a(a+1)(3b-a+1)}{6} $
Altra bonus question: Si può generalizzare e stabilire quanti rettangolini di base k e altezza hk si possono individuare nella quadrettatura? Il nostro problema sarebbe con $ h=1 $

Federiko ha scritto:Giusto! E per ndp15 scrivo le sommatorie:
$ \displaystyle \sum_{i=0}^{a-1}(a-i)(b-i)=\sum_{i=0}^{a-1}(ab-(a+b)i+i^2)=a^2b-\frac{a(a-1)(a+b)}{2}+\frac{a(a-1)(2a-1)}{6}=\frac{a(a+1)(3b-a+1)}{6} $
Altra bonus question: Si può generalizzare e stabilire quanti rettangolini di base k e altezza hk si possono individuare nella quadrettatura? Il nostro problema sarebbe con $ h=1 $

Le due sommatorie sarei anche riuscito a scriverle in maniera corretta, ma non sarei riuscito a fare il 3° passaggio. Conosci per caso qualche buona dispensa in cui mi spiegano come si passa da una sommatoria alla relativa formula chiusa (sempre che si possa fare)?
Comunque grazie!

Non c'è una formula magica per passare da una sommatoria a una formula chiusa. Ci sono però delle cose da tenere a mente, come ad esempio

$ $\sum_i[f(i)+g(i)]=\sum_i f(i)+\sum_i g(i)$ $

$ $\sum_i [k\cdot f(i)]=k \sum_i f(i)$ $

$ $\sum_{i=0}^{n} i=\frac{n(n+1)}{2}$ $

$ $\sum_{i=0}^{n} i^2=\frac{n(n+1)(2n+1)}{6}$ $

$ $\sum_{i=0}^{n} i^3=\Big[\frac{n(n+1)}{2}\Big]^2$ $

ecc.

$ $\sum_{i=0}^{n} (2i+1)=(n+1)^2$ $

$ $\sum_{i=0}^{n} k^i=\frac{k^{n+1}-1}{k-1}$ $

Federiko ha scritto:Altra bonus question: Si può generalizzare e stabilire quanti rettangolini di base k e altezza hk si possono individuare nella quadrettatura? Il nostro problema sarebbe con $ h=1 $

Mi viene
$ $\displaystyle\sum_{k=1}^{\lfloor\dfrac{a}{h}\rfloor} (b-k+1)(a-kh+1) +\sum_{k=1}^{\lfloor\dfrac{b}{h}\rfloor} (a-k+1)(b-kh+1)$ $