Pytanie brzmi:
Na ile sposobów można ustawić X wież na szachownicy o wymiarach X na X tak, aby żadna nie była w zasięgu bicia innej, jeżeli będziemy korzystać tylko z pięciu równoległych przekątnych (pola zaznaczone na przykładowym rysunku dla X=5)?
Wieże na szachownicy
-
mestali
- Użytkownik
- Posty: 32
- Rejestracja: 23 lis 2009, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Pomógł: 5 razy
Wieże na szachownicy
Stawiając jedną wieżę gdziekolwiek redukujesz dokladnie 1 wiersz i dokladnie jedną kolumną. Oznacza to, że możesz postawić X wież,
sposób obliczania jest następujący:
1 wieżę możesz postawić na \(\displaystyle{ X^2}\) polach
2 wieżę możesz postawić już na \(\displaystyle{ (X-1)^2}\) polach
itd...
Jeśli więc pytasz o ilość możliwości będzie to:
\(\displaystyle{ \prod_{i=0}^{n-1}(X-i)^2=(X!)^2}\)
sposób obliczania jest następujący:
1 wieżę możesz postawić na \(\displaystyle{ X^2}\) polach
2 wieżę możesz postawić już na \(\displaystyle{ (X-1)^2}\) polach
itd...
Jeśli więc pytasz o ilość możliwości będzie to:
\(\displaystyle{ \prod_{i=0}^{n-1}(X-i)^2=(X!)^2}\)
Ostatnio zmieniony 23 gru 2009, o 13:08 przez miki999, łącznie zmieniany 1 raz.
Powód: Reklama...
Powód: Reklama...
-
abc666
Wieże na szachownicy
Ma ktoś jakiś pomył na to zadanie?
Jak coś to policzyłem programem kilka początkowych wartości (raczej są ok):
\(\displaystyle{ \begin{tabular}{|c|c|c|c|}\hline
n & n! & \mbox{dobre} & \mbox{złe} \\ \hline \hline
4 & 24 & 14 & 10 \\ \hline
5 & 120 & 31 & 89 \\ \hline
6 & 720 & 73 & 647 \\ \hline
7 & 5040 & 172 & 4868 \\ \hline
8 & 40320 & 400 & 39920 \\
\hline \end{tabular}}\)
dobre to nasze wartości, natomiast złe to pozostałe permutacje nie mieszczące się na 5 przekątnych
-- 24 grudnia 2009, 20:22 --
Znalazłem tą sekwencję
Mógłby ktoś coś napisać na ten temat?
nevermoon, skąd masz to zadanie? Bo jak widać np. tutaj ... 08-376.pdf nie jest on tak banalny
Jak coś to policzyłem programem kilka początkowych wartości (raczej są ok):
\(\displaystyle{ \begin{tabular}{|c|c|c|c|}\hline
n & n! & \mbox{dobre} & \mbox{złe} \\ \hline \hline
4 & 24 & 14 & 10 \\ \hline
5 & 120 & 31 & 89 \\ \hline
6 & 720 & 73 & 647 \\ \hline
7 & 5040 & 172 & 4868 \\ \hline
8 & 40320 & 400 & 39920 \\
\hline \end{tabular}}\)
dobre to nasze wartości, natomiast złe to pozostałe permutacje nie mieszczące się na 5 przekątnych
-- 24 grudnia 2009, 20:22 --
Znalazłem tą sekwencję
Mógłby ktoś coś napisać na ten temat?
nevermoon, skąd masz to zadanie? Bo jak widać np. tutaj ... 08-376.pdf nie jest on tak banalny
-
MichalKulis
- Użytkownik
- Posty: 47
- Rejestracja: 19 sty 2011, o 08:15
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
Wieże na szachownicy
mam rozwiązanie.
oznaczmy: \(\displaystyle{ R(n)}\) = liczba rozwiązań dla szachownicy \(\displaystyle{ n \cdot n}\).
ustalmy początkowe wartości:
\(\displaystyle{ R(0) = 1}\) (umówmy się tak!)
\(\displaystyle{ R(1) = 1\\
R(2) = 2\\
R(3) = 6}\)
a dalej:
\(\displaystyle{ R(n) = R(n-1) + R(n-2) + R(n-3) + R(n-4) + 2 \sum_{k=0}^{n-3} R(k)}\)
Rozwiązanie jest niemal pewne choć formalnego dowodu nie przedstawię, bo zajęłoby to zbyt dużo miejsca. Najlepiej to widać patrząc na szachownicę.
Czy ktoś wie jak taki wzór rekurencyjny przekształcić na ogólny?
Bo sądząc po ciągu Fibonacci'ego nie będzie to zbyt łatwe.
-- 22 sie 2011, o 12:29 --
a co ciekawe to lim\(\displaystyle{ \frac{R(n+1)}{R(n)}\approx2,333554}\) więc można użyć przybliżonego wzoru ogólnego dla dostatecznie dużych n.
mam wrażenie, że ten limes to jakaś liczba niewymierna.
-- 24 sie 2011, o 14:39 --
ten poprzedni wzór na R(n) można przekształcić do nieco zgrabniejszej postaci:
\(\displaystyle{ R(n)=2 \cdot R(n-1)+2 \cdot R(n-3)-R(n-5)}\)
teraz pytanie, czy to ułatwia uzyskanie wzoru ogólnego? Może komuś uda się to zrobić za pomocą funkcji tworzących?
oznaczmy: \(\displaystyle{ R(n)}\) = liczba rozwiązań dla szachownicy \(\displaystyle{ n \cdot n}\).
ustalmy początkowe wartości:
\(\displaystyle{ R(0) = 1}\) (umówmy się tak!)
\(\displaystyle{ R(1) = 1\\
R(2) = 2\\
R(3) = 6}\)
a dalej:
\(\displaystyle{ R(n) = R(n-1) + R(n-2) + R(n-3) + R(n-4) + 2 \sum_{k=0}^{n-3} R(k)}\)
Rozwiązanie jest niemal pewne choć formalnego dowodu nie przedstawię, bo zajęłoby to zbyt dużo miejsca. Najlepiej to widać patrząc na szachownicę.
Czy ktoś wie jak taki wzór rekurencyjny przekształcić na ogólny?
Bo sądząc po ciągu Fibonacci'ego nie będzie to zbyt łatwe.
-- 22 sie 2011, o 12:29 --
a co ciekawe to lim\(\displaystyle{ \frac{R(n+1)}{R(n)}\approx2,333554}\) więc można użyć przybliżonego wzoru ogólnego dla dostatecznie dużych n.
mam wrażenie, że ten limes to jakaś liczba niewymierna.
-- 24 sie 2011, o 14:39 --
ten poprzedni wzór na R(n) można przekształcić do nieco zgrabniejszej postaci:
\(\displaystyle{ R(n)=2 \cdot R(n-1)+2 \cdot R(n-3)-R(n-5)}\)
teraz pytanie, czy to ułatwia uzyskanie wzoru ogólnego? Może komuś uda się to zrobić za pomocą funkcji tworzących?
Ostatnio zmieniony 22 sie 2011, o 16:32 przez Lbubsazob, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Całe wyrażenia matematyczne umieszczaj w tagach[latex] [/latex]
Powód: Poprawa wiadomości. Całe wyrażenia matematyczne umieszczaj w tagach
-
MichalKulis
- Użytkownik
- Posty: 47
- Rejestracja: 19 sty 2011, o 08:15
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
Wieże na szachownicy
To się klei. W tym linku mamy bowiem "Number of permutations of length n within distance 2 of a fixed permutation"abc666 pisze: Znalazłem tą sekwencję
Mógłby ktoś coś napisać na ten temat?
Czym jest odległość dwóch permutacji p i q?
\(\displaystyle{ d(p, q) = max |p _{j} - q _{j}| : j=1,2,...,n}\)
No to czym jest nasze zadanie? De facto, jest pytaniem o liczbę permutacji długości n odległych o co najwyżej 2 od permutacji w której wiersze (1,2,3,4,5) przechodzą na kolumny (5,4,3,2,1).