Ile spośród wszystkich prostokątów na kracie jest kwadratami

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
edaro
Użytkownik
Użytkownik
Posty: 268
Rejestracja: 18 gru 2006, o 20:01
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 56 razy
Pomógł: 16 razy

Ile spośród wszystkich prostokątów na kracie jest kwadratami

Post autor: edaro »

Ile spośród wszystkich prostokątów, które można utworzyć na kracie n × n, jest kwadratami?

Wiem, że wszystkich prostokątów można na kracie n x n utworzyć \(\displaystyle{ {n + 1 \choose 2}^2}\)
tylko nie mam pomysłu, jak od tego odjąć liczbę prostokątów, które nie są kwadratami lub bezpośrednio jak obliczyć ilość samych kwadratów?
Jedyne co mi przychodzi do głowy to, że różnica numerów lini w kracie musi być sobie równa (aby prostokąt był kwadratem), czyli \(\displaystyle{ x_{2} - x_{1} = y_{2} - y_{1}}\), gdzie x i y to numery lini na kracie (takich numerów jest n + 1 - od 0 do n).
abc666

Ile spośród wszystkich prostokątów na kracie jest kwadratami

Post autor: abc666 »

Kwadratów o boku 1 jest \(\displaystyle{ n^2}\). Kwadratów o boku 2 jest \(\displaystyle{ (n-1)^2}\). ... Jest jeden kwadrat o boku \(\displaystyle{ n}\). W sumie
\(\displaystyle{ n^2+(n-1)^2+..+1^2=\frac{n(n+1)(2n+1)}{6}}\)
edaro
Użytkownik
Użytkownik
Posty: 268
Rejestracja: 18 gru 2006, o 20:01
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 56 razy
Pomógł: 16 razy

Ile spośród wszystkich prostokątów na kracie jest kwadratami

Post autor: edaro »

Tak też można, ale interesuje mnie jednak inny sposób.
abc666

Ile spośród wszystkich prostokątów na kracie jest kwadratami

Post autor: abc666 »

A jest jakiś konkretny powód szukania trudniejszego rozwiązania? Czy to jest część jakiegoś większego zadania?
ODPOWIEDZ