szukanie zaawansowane
 [ Posty: 7 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: kwadrat nxn
PostNapisane: 6 paź 2014, o 00:37 
Użytkownik

Posty: 1068
Lokalizacja: Warszawa
Cześć ;)
Dany jest kwadrat n \times n. Na ile sposobów możemy wybrać z niego wszystkie prostokąty tak, ma wierzchołki "w punktach kratowych"- mam nadzieję, że wiadomo o co chodzi.

Wybieramy punkty, które łączy przekątna. Tak wyzcznaone punkty określają nam prostokąt.
No to pierwszy punkt wybieram na n^2 sposobów. W kolejnym punkcie współrzędne nie mogą być takie same, toteż wybieram na (n-1)(n-1) Ostateczna odpowiedź brzmi:
n^2(n-1)(n-1)
Prawidłowa odpowiedź to: {n+1 \choose 2} ^2
Gdzie jest błąd w rozumowaniu.
Góra
Mężczyzna Offline
 Tytuł: kwadrat nxn
PostNapisane: 6 paź 2014, o 00:58 
Użytkownik
Avatar użytkownika

Posty: 246
Lokalizacja: Warszawa
Błąd jest m. in. taki, że każdy prostokąt wybierasz Twoim sposobem 2 razy, bo on ma dwie przekątne.

Po drugie, każdą przekątną wybierasz dwa razy, bo jak mamy 2 konkretne punkty spełniające założenia, to raz do pierwszego dobrałeś drugi, a później do drugiego pierwszy, a to ta sama przekątna.

Po trzecie - prostokąty mogą być "pochylone" (?)

Po czwarte - chyba nie rozumiem treści zadania, albo poprawna odpowiedź nie działa dla n=2.

Warto dla małych n sobie testować "kandydatów na ostateczny wzór".
Góra
Mężczyzna Offline
 Tytuł: kwadrat nxn
PostNapisane: 6 paź 2014, o 09:07 
Użytkownik

Posty: 1068
Lokalizacja: Warszawa
dobrze, to poproszę o wskazówkę przy tym zadaniu :)
Góra
Mężczyzna Offline
 Tytuł: kwadrat nxn
PostNapisane: 6 paź 2014, o 09:41 
Gość Specjalny
Avatar użytkownika

Posty: 4974
Lokalizacja: Lozanna
Twoje rozwiązanie jest poprawne, zauważ jednak, że każdy prostokąt zliczasz 4 razy, zatem Twój wynik musisz podzielić przez 4, co da poprawną odpowiedź.
Góra
Mężczyzna Offline
 Tytuł: kwadrat nxn
PostNapisane: 6 paź 2014, o 10:21 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
mm34639 napisał(a):
Po czwarte - chyba nie rozumiem treści zadania, albo poprawna odpowiedź nie działa dla n=2
Zordon napisał(a):
Twoje rozwiązanie jest poprawne, zauważ jednak, że każdy prostokąt zliczasz 4 razy, zatem Twój wynik musisz podzielić przez 4, co da poprawną odpowiedź.
Poprawna odpowiedź to \binom{n+1}{2}^2 - warto bowiem zauważyć, że kwadrat n\times n ma (n+1)^2 punktów kratowych. Stąd w rozumowaniu tukanika brakuje nie tylko czwórki w mianowniku, ale także dodania do każdego n jedynki.

Oczywiście to przy założeniu, że uwzględniamy tylko prostokąty o bokach równoległych/prostopadłych do osi układu.

Q.
Góra
Mężczyzna Offline
 Tytuł: kwadrat nxn
PostNapisane: 6 paź 2014, o 16:06 
Użytkownik

Posty: 1068
Lokalizacja: Warszawa
ok, a w przypadku uzasadnienia, że
1^3 + 2^3 + ... + n^3
Trzeba uzasadanić jakoś kombinatorycznie, że to jest równe liczbie prostokątów jak powyżej.

Próbowałem już ze 3h. Wydawało mi się, że może uda mi się do tego jakoś wciągnąć ciągi 3-elementowe, ale nic nie wyniosłem.
Góra
Mężczyzna Offline
 Tytuł: kwadrat nxn
PostNapisane: 6 paź 2014, o 18:00 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
Rozważmy n kwadratów o wymiarach k\times k dla k=1,2,\ldots ,n takich, że każdy zawiera dolny lewy róg całego kwadratu n\times n. Oznaczmy k-ty taki kwadrat przez T_k.

Policzmy ile jest pasujących prostokątów takich, że najmniejszy kwadrat z podanych w jakim się zawierają to T_k. Wszystkich pasujących prostokątów zawartych w T_k jest jak już wiadomo \binom{k+1}{2}^2. Od tej liczby musimy jednak odjąć te pasujące prostokąty, które mieszczą się w kwadracie T_{k-1}, a tych jest \binom k2^2. Ogólnie więc prostokątów mieszczących się w T_k, ale nie w T_{k-1} jest:
\binom{k+1}{2}^2-\binom k2^2= \left( \binom{k+1}{2}-\binom k2\right) \left( \binom{k+1}{2}+\binom k2\right) = \\ =  \binom k1 \cdot \frac{(k+1)k + k(k-1)}{2} = k^3.

Stąd łatwo wynika teza.

Q.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 7 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Kwadrat podzielony na mniejsze  Lucky09  6
 Kwadrat w wielu barwach  andrewto21  6
 Kwadrat relacji  kernelek  1
 Kwadrat sumy dwumianu Newtona  Amitiel  1
 Kwadrat wpisany w trójkąt równoboczny  Vanguard  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl