Quanti quadrati? (own)

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Federiko
Messaggi: 226
Iscritto il: 15 mag 2008, 19:24
Località: Roma

Quanti quadrati? (own)

Messaggio da Federiko » 13 apr 2009, 20:48

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 :D
CUCCIOLO

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 13 apr 2009, 21:53

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.

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Messaggio da ndp15 » 13 apr 2009, 22:52

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 ( :roll: ) 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.

GioacchinoA
Messaggi: 137
Iscritto il: 13 feb 2009, 15:44
Località: Bari

Messaggio da GioacchinoA » 13 apr 2009, 23:37

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)) $

Avatar utente
Federiko
Messaggi: 226
Iscritto il: 15 mag 2008, 19:24
Località: Roma

Messaggio da Federiko » 14 apr 2009, 11:52

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 $
CUCCIOLO

ndp15
Messaggi: 598
Iscritto il: 18 gen 2007, 19:01

Messaggio da ndp15 » 14 apr 2009, 12:09

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!

fede90
Messaggi: 287
Iscritto il: 04 apr 2007, 21:36
Località: Udine

Messaggio da fede90 » 14 apr 2009, 14:36

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}$ $
Bene, prendiamo un pentagono di [tex]$n$[/tex] lati...

GioacchinoA
Messaggi: 137
Iscritto il: 13 feb 2009, 15:44
Località: Bari

Messaggio da GioacchinoA » 15 apr 2009, 00:25

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)$ $

Rispondi