Silnia przedstawiona jako suma kolejnych liczb
-
Konikov
- Użytkownik
- Posty: 497
- Rejestracja: 13 mar 2008, o 18:56
- Płeć: Mężczyzna
- Lokalizacja: z całki tego świata
- Podziękował: 66 razy
- Pomógł: 44 razy
Silnia przedstawiona jako suma kolejnych liczb
Oblicz, na ile sposobów można przedstawić \(\displaystyle{ 10!}\) jako sumę kolejnych liczb całkowitych.
-
abc666
Silnia przedstawiona jako suma kolejnych liczb
Rozważmy postać danej sumy składającej się z \(\displaystyle{ a}\) liczb. Jeśli \(\displaystyle{ a}\) jest nieparzyste to suma jest postaci \(\displaystyle{ a\cdot n}\) przy czym najmniejsza liczba jaką możemy otrzymać to \(\displaystyle{ \frac{a(a+1)}{2}}\). Każdą większą bądź równą już się da.
Postaci liczby \(\displaystyle{ 10!}\) takich jak powyżej jest \(\displaystyle{ {4 \choose 1} +{4 \choose 2}+ {4 \choose 3}+ {4 \choose 4}}\)
Bo mamy w rozkładzie 4 czynniki nieparzyste \(\displaystyle{ \{3,5,7,9\}}\) a \(\displaystyle{ \frac{(3\cdot 5\cdot 7\cdot 9)(3\cdot 5\cdot 7\cdot 9+1)}{2}<10!}\)
Jeżeli \(\displaystyle{ a}\) jest parzyste to suma liczb jest postaci
\(\displaystyle{ an+\frac{a}{2}}\)
a najmniejsza możliwa do otrzymania liczba jest taka jak poprzednio.
Niech \(\displaystyle{ a=2b}\) wtedy dostajemy
\(\displaystyle{ 2bn+b=10!\\
b(2n+1)=10!}\)
Musimy znaleźć liczbę rozwiązań tego równania w liczba naturalnych (bez zera).
\(\displaystyle{ (2n+1)}\) jest nieparzyste więc znowu rozwiązań będzie \(\displaystyle{ {4 \choose 1} +{4 \choose 2}+ {4 \choose 3}+ {4 \choose 4}}\) z identycznego powodu jak wczesniej.
Dodajmy jeszcze samo \(\displaystyle{ 10!}\) jako sumę jednej liczby i dostajemy w sumie \(\displaystyle{ 2^5-1}\) możliwych postaci.
*Jeśli się gdzieś nie pomyliłem.
Postaci liczby \(\displaystyle{ 10!}\) takich jak powyżej jest \(\displaystyle{ {4 \choose 1} +{4 \choose 2}+ {4 \choose 3}+ {4 \choose 4}}\)
Bo mamy w rozkładzie 4 czynniki nieparzyste \(\displaystyle{ \{3,5,7,9\}}\) a \(\displaystyle{ \frac{(3\cdot 5\cdot 7\cdot 9)(3\cdot 5\cdot 7\cdot 9+1)}{2}<10!}\)
Jeżeli \(\displaystyle{ a}\) jest parzyste to suma liczb jest postaci
\(\displaystyle{ an+\frac{a}{2}}\)
a najmniejsza możliwa do otrzymania liczba jest taka jak poprzednio.
Niech \(\displaystyle{ a=2b}\) wtedy dostajemy
\(\displaystyle{ 2bn+b=10!\\
b(2n+1)=10!}\)
Musimy znaleźć liczbę rozwiązań tego równania w liczba naturalnych (bez zera).
\(\displaystyle{ (2n+1)}\) jest nieparzyste więc znowu rozwiązań będzie \(\displaystyle{ {4 \choose 1} +{4 \choose 2}+ {4 \choose 3}+ {4 \choose 4}}\) z identycznego powodu jak wczesniej.
Dodajmy jeszcze samo \(\displaystyle{ 10!}\) jako sumę jednej liczby i dostajemy w sumie \(\displaystyle{ 2^5-1}\) możliwych postaci.
*Jeśli się gdzieś nie pomyliłem.
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Silnia przedstawiona jako suma kolejnych liczb
Nie rozumiem tego rozwiązania już od tego miejsca.abc666 pisze:Rozważmy postać danej sumy składającej się z \(\displaystyle{ a}\) liczb. Jeśli \(\displaystyle{ a}\) jest nieparzyste to suma jest postaci \(\displaystyle{ a\cdot n}\) przy czym najmniejsza liczba jaką możemy otrzymać to \(\displaystyle{ \frac{a(a+1)}{2}}\). Każdą większą bądź równą już się da.
W każdym razie według mnie prawidłowa odpowiedź to \(\displaystyle{ 60}\) (a zadanie pochodzi z egzaminu z dyskretnej w 2009 roku, informatyka MIMUW).
Q.
-
abc666
Silnia przedstawiona jako suma kolejnych liczb
Znalazłem błąd w swoim rozumowaniu i teraz postaram się to lepiej napisać.
Rozpatrujemy to z ilu składników składa się suma. Jeśli liczba składników sumy kolejnych liczb naturalnych jest nieparzysta i składników tych jest dokładnie \(\displaystyle{ k}\) to można ją przedstawić jako \(\displaystyle{ kn}\) gdzie \(\displaystyle{ n\in N}\).
Najmniejsza liczba jaką możemy otrzymać sumując \(\displaystyle{ k}\) kolejnych liczb to \(\displaystyle{ \frac{k(k+1)}{2}}\) (gdy sumujemy od jedynki). Każdą liczbę postaci \(\displaystyle{ kn}\) która jest większa bądź równa \(\displaystyle{ \frac{k(k+1)}{2}}\) możemy uzyskać poprzez takie sumowanie (bo "przesuwając" sumę o jedną liczbę zwiększamy ją o \(\displaystyle{ k}\)). Teraz musimy policzyć liczbę sposobów przedstawienia liczby \(\displaystyle{ 10!}\) jako \(\displaystyle{ kn}\) gdzie \(\displaystyle{ k}\) jest nieparzyste. W rozkładzie \(\displaystyle{ 10!}\) mamy takie nieparzyste składniki \(\displaystyle{ 3^45^27}\) (3,5,7, 2 trójki z 9, trójka z 6 i 5 z dziesiątki).
Przedstawień takich jest 30. (Można to obliczyć sumując współczynniki wielomianu \(\displaystyle{ (1+x+x^2+x^3+x^4)(1+x+x^2)(1+x)}\). Dodany mamy też tutaj przypadek gdy sumujemy samo \(\displaystyle{ 10!}\)). Jednak 3 przedstawienia nam odpadają bo:
\(\displaystyle{ 3^4\cdot 5^2\cdot 7>3^3\cdot 5^2\cdot 7>3^4\cdot 5\cdot 7=2835}\)
a \(\displaystyle{ \frac{1}{2}\cdot 2835\cdot 2836>10!}\)
Czyli pozostaje 27 przedstawień.
Teraz musimy rozpatrzeć przypadek, gdy \(\displaystyle{ k}\) jest parzyste. Oznaczmy \(\displaystyle{ k=2m}\), wtedy suma k kolejnych liczb ma postać
\(\displaystyle{ 2mn+m}\) gdzie \(\displaystyle{ n\in N}\)
Musimy więc znaleźć liczbę rozwiązań równania diofantycznego (*) pamiętając o warunku, że
\(\displaystyle{ \frac{k(k+1)}{2}\le 10!}\)
\(\displaystyle{ 2mn+m=10! \quad (*) \\
m(2n+1)=10!=2^8\cdot 3^4\cdot 5^2\cdot 7}\)
Czyli \(\displaystyle{ m\ge 2^8}\) więc \(\displaystyle{ k\ge 2^9}\). Teraz gdy zauważymy, że
\(\displaystyle{ \frac{1}{2}(2^9\cdot 5 )(2^9\cdot 5 +1)=3278080<10!}\)
oraz
\(\displaystyle{ \frac{1}{2}(2^9\cdot 7 )(2^9\cdot 7 +1)>10!}\)
dostajemy iż \(\displaystyle{ k}\) może przyjąć tylko wartości ze zbioru \(\displaystyle{ \{2^9,2^9\cdot3,2^9\cdot5\}}\) co daje nam 3 przedstawienia.
Czyli w sumie mamy 30 możliwych przedstawień.
W pierwszym rozwiązaniu zapomniałem o nieparzystych składnikach z rozkładu 6 i 10 oraz zapomniałem o rozkładzie 9 na dwie trójki. Przypadek parzysty był tam całkiem skopany. Reszta pozostała bez zmian. Mam nadzieje, że teraz jest zrozumiale i poprawnie.
Rozpatrujemy to z ilu składników składa się suma. Jeśli liczba składników sumy kolejnych liczb naturalnych jest nieparzysta i składników tych jest dokładnie \(\displaystyle{ k}\) to można ją przedstawić jako \(\displaystyle{ kn}\) gdzie \(\displaystyle{ n\in N}\).
Najmniejsza liczba jaką możemy otrzymać sumując \(\displaystyle{ k}\) kolejnych liczb to \(\displaystyle{ \frac{k(k+1)}{2}}\) (gdy sumujemy od jedynki). Każdą liczbę postaci \(\displaystyle{ kn}\) która jest większa bądź równa \(\displaystyle{ \frac{k(k+1)}{2}}\) możemy uzyskać poprzez takie sumowanie (bo "przesuwając" sumę o jedną liczbę zwiększamy ją o \(\displaystyle{ k}\)). Teraz musimy policzyć liczbę sposobów przedstawienia liczby \(\displaystyle{ 10!}\) jako \(\displaystyle{ kn}\) gdzie \(\displaystyle{ k}\) jest nieparzyste. W rozkładzie \(\displaystyle{ 10!}\) mamy takie nieparzyste składniki \(\displaystyle{ 3^45^27}\) (3,5,7, 2 trójki z 9, trójka z 6 i 5 z dziesiątki).
Przedstawień takich jest 30. (Można to obliczyć sumując współczynniki wielomianu \(\displaystyle{ (1+x+x^2+x^3+x^4)(1+x+x^2)(1+x)}\). Dodany mamy też tutaj przypadek gdy sumujemy samo \(\displaystyle{ 10!}\)). Jednak 3 przedstawienia nam odpadają bo:
\(\displaystyle{ 3^4\cdot 5^2\cdot 7>3^3\cdot 5^2\cdot 7>3^4\cdot 5\cdot 7=2835}\)
a \(\displaystyle{ \frac{1}{2}\cdot 2835\cdot 2836>10!}\)
Czyli pozostaje 27 przedstawień.
Teraz musimy rozpatrzeć przypadek, gdy \(\displaystyle{ k}\) jest parzyste. Oznaczmy \(\displaystyle{ k=2m}\), wtedy suma k kolejnych liczb ma postać
\(\displaystyle{ 2mn+m}\) gdzie \(\displaystyle{ n\in N}\)
Musimy więc znaleźć liczbę rozwiązań równania diofantycznego (*) pamiętając o warunku, że
\(\displaystyle{ \frac{k(k+1)}{2}\le 10!}\)
\(\displaystyle{ 2mn+m=10! \quad (*) \\
m(2n+1)=10!=2^8\cdot 3^4\cdot 5^2\cdot 7}\)
Czyli \(\displaystyle{ m\ge 2^8}\) więc \(\displaystyle{ k\ge 2^9}\). Teraz gdy zauważymy, że
\(\displaystyle{ \frac{1}{2}(2^9\cdot 5 )(2^9\cdot 5 +1)=3278080<10!}\)
oraz
\(\displaystyle{ \frac{1}{2}(2^9\cdot 7 )(2^9\cdot 7 +1)>10!}\)
dostajemy iż \(\displaystyle{ k}\) może przyjąć tylko wartości ze zbioru \(\displaystyle{ \{2^9,2^9\cdot3,2^9\cdot5\}}\) co daje nam 3 przedstawienia.
Czyli w sumie mamy 30 możliwych przedstawień.
W pierwszym rozwiązaniu zapomniałem o nieparzystych składnikach z rozkładu 6 i 10 oraz zapomniałem o rozkładzie 9 na dwie trójki. Przypadek parzysty był tam całkiem skopany. Reszta pozostała bez zmian. Mam nadzieje, że teraz jest zrozumiale i poprawnie.
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Silnia przedstawiona jako suma kolejnych liczb
Rozumowania na razie nie prześledziłem, ale wynik jest już prawie dobry. "Prawie", to znaczy z zastrzeżeniem, że chodziło o sumę kolejnych liczb całkowitych, a nie naturalnych. A równość:
\(\displaystyle{ 3+4+5+6= (-2)+(-1)+0+1+2+3+4+5+6}\)
w połączeniu z nietrudnym faktem, że suma nie może się zaczynać od zera ani jedynki - pokazują, że liczbę trzydzieści należy pomnożyć jeszcze przez dwa.
Moje rozwiązanie było zupełnie inne, jeśli jest zapotrzebowanie, to mogę wkleić.
Q.
\(\displaystyle{ 3+4+5+6= (-2)+(-1)+0+1+2+3+4+5+6}\)
w połączeniu z nietrudnym faktem, że suma nie może się zaczynać od zera ani jedynki - pokazują, że liczbę trzydzieści należy pomnożyć jeszcze przez dwa.
Moje rozwiązanie było zupełnie inne, jeśli jest zapotrzebowanie, to mogę wkleić.
Q.
-
abc666
Silnia przedstawiona jako suma kolejnych liczb
Aj, cały czas widziałem tam naturalne . Oczywiście masz racje.
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Silnia przedstawiona jako suma kolejnych liczb
Moje rozwiązanie sprzed roku (teraz poprawiłem tylko literówkę):
Zadanie
Na ile sposobów można przedstawić liczbę 10! jako sumę kolejnych liczb całkowitych?
Rozwiązanie
Zauważmy najpierw, że te kolejne liczby całkowite nie mogą się zaczynać od zera ani od jedynki, w przeciwnym razie bowiem dla pewnego \(\displaystyle{ n}\) mielibyśmy \(\displaystyle{ 10! = 1+ 2+ \dots + n = \frac{n(n+1)}{2}}\), czyli \(\displaystyle{ 2^9\cdot 3^4 \cdot 5^2 \cdot 7 = n(n+1)}\). To zaś jest niemożliwe, bo z dwóch kolejnych liczb całkowitych tylko jedna może być podzielna przez \(\displaystyle{ k}\) dla \(\displaystyle{ k=2,3,5,7}\), więc musi być \(\displaystyle{ n=2^{9a_1}\cdot 3^{4a_2} \cdot 5^{2a_3} \cdot 7^{a_4}}\) dla \(\displaystyle{ a_i\in \{ 0,1 \}}\), a to jak łatwo ręcznie sprawdzić prowadzi do sprzeczności.
Zauważmy też, że wystarczy znaleźć ilość rozwiązań, w których zaczynamy sumowanie od liczby dodatniej - i tę ilość pomnożyć przez dwa. Dowód przez przykład
\(\displaystyle{ 3+4+5 = (-2) + (-1) + 0 + 1+ 2+ 3+ 4+ 5}\)
Jeśli więc rzeczone kolejne liczby zaczynają się od liczby większej od jeden, to każdą taką sumę kolejnych liczb da się przedstawić jako \(\displaystyle{ \sum_{i=1}^{m} i - \sum_{i=1}^{n} i}\) dla pewnych całkowitych \(\displaystyle{ m>n}\), przy czym przedstawienie jest jednoznaczne. Zatem ilość rozwiązań jest równa ilości par liczb całkowitych \(\displaystyle{ (m,n)}\) takich, że \(\displaystyle{ m>n}\) oraz:
\(\displaystyle{ 10! = \frac{m(m+1)}{2} - \frac{n(n+1)}{2}}\)
lub równoważnie:
\(\displaystyle{ 2^9\cdot 3^4 \cdot 5^2 \cdot 7 = (m+n+1)(m-n)}\)
Ponieważ nawiasy są różnej parzystości, więc pytamy po prostu ile jest rozkładów liczby po lewej stronie na iloczyn dwóch liczb różnej parzystości (po czym większa z tych liczb to będzie \(\displaystyle{ m+n+1}\), a mniejsza to \(\displaystyle{ m-n}\)). Jeśli mają być różnej parzystości, to w jednym czynniku nie występuje żadna dwójka, jest więc to czynnik postaci: \(\displaystyle{ 3^{a_1} \cdot 5^{a_2} \cdot 7^{a_3}}\), gdzie \(\displaystyle{ a_1 \in \{ 0,1,2,3,4 \}, a_2 \in \{ 0,1,2 \} , a_3 \in \{ 0,1 \}}\). Takich czynników jest oczywiście \(\displaystyle{ 5 \cdot 3 \cdot 2 = 30}\), tyle więc jest szukanych rozkładów.
Jak pamiętamy, tę ilość należało pomnożyć jeszcze przez dwa, zatem ostateczna odpowiedź to \(\displaystyle{ 60}\).
Zadanie
Na ile sposobów można przedstawić liczbę 10! jako sumę kolejnych liczb całkowitych?
Rozwiązanie
Zauważmy najpierw, że te kolejne liczby całkowite nie mogą się zaczynać od zera ani od jedynki, w przeciwnym razie bowiem dla pewnego \(\displaystyle{ n}\) mielibyśmy \(\displaystyle{ 10! = 1+ 2+ \dots + n = \frac{n(n+1)}{2}}\), czyli \(\displaystyle{ 2^9\cdot 3^4 \cdot 5^2 \cdot 7 = n(n+1)}\). To zaś jest niemożliwe, bo z dwóch kolejnych liczb całkowitych tylko jedna może być podzielna przez \(\displaystyle{ k}\) dla \(\displaystyle{ k=2,3,5,7}\), więc musi być \(\displaystyle{ n=2^{9a_1}\cdot 3^{4a_2} \cdot 5^{2a_3} \cdot 7^{a_4}}\) dla \(\displaystyle{ a_i\in \{ 0,1 \}}\), a to jak łatwo ręcznie sprawdzić prowadzi do sprzeczności.
Zauważmy też, że wystarczy znaleźć ilość rozwiązań, w których zaczynamy sumowanie od liczby dodatniej - i tę ilość pomnożyć przez dwa. Dowód przez przykład
\(\displaystyle{ 3+4+5 = (-2) + (-1) + 0 + 1+ 2+ 3+ 4+ 5}\)
Jeśli więc rzeczone kolejne liczby zaczynają się od liczby większej od jeden, to każdą taką sumę kolejnych liczb da się przedstawić jako \(\displaystyle{ \sum_{i=1}^{m} i - \sum_{i=1}^{n} i}\) dla pewnych całkowitych \(\displaystyle{ m>n}\), przy czym przedstawienie jest jednoznaczne. Zatem ilość rozwiązań jest równa ilości par liczb całkowitych \(\displaystyle{ (m,n)}\) takich, że \(\displaystyle{ m>n}\) oraz:
\(\displaystyle{ 10! = \frac{m(m+1)}{2} - \frac{n(n+1)}{2}}\)
lub równoważnie:
\(\displaystyle{ 2^9\cdot 3^4 \cdot 5^2 \cdot 7 = (m+n+1)(m-n)}\)
Ponieważ nawiasy są różnej parzystości, więc pytamy po prostu ile jest rozkładów liczby po lewej stronie na iloczyn dwóch liczb różnej parzystości (po czym większa z tych liczb to będzie \(\displaystyle{ m+n+1}\), a mniejsza to \(\displaystyle{ m-n}\)). Jeśli mają być różnej parzystości, to w jednym czynniku nie występuje żadna dwójka, jest więc to czynnik postaci: \(\displaystyle{ 3^{a_1} \cdot 5^{a_2} \cdot 7^{a_3}}\), gdzie \(\displaystyle{ a_1 \in \{ 0,1,2,3,4 \}, a_2 \in \{ 0,1,2 \} , a_3 \in \{ 0,1 \}}\). Takich czynników jest oczywiście \(\displaystyle{ 5 \cdot 3 \cdot 2 = 30}\), tyle więc jest szukanych rozkładów.
Jak pamiętamy, tę ilość należało pomnożyć jeszcze przez dwa, zatem ostateczna odpowiedź to \(\displaystyle{ 60}\).
-
aleksyprycki
- Użytkownik
- Posty: 9
- Rejestracja: 17 sie 2010, o 14:47
- Płeć: Mężczyzna
- Lokalizacja: Baranowo
- Pomógł: 1 raz
Silnia przedstawiona jako suma kolejnych liczb
Ja też poproszę o inne rozwiązanie bo tego chyba nie ogarniam. Ja kombinowałem jakoś z sumą ciągu arytmetycznego i kiedyś pamiętam, że nawet wpadłem na to co i jak ale to na pewno nie było tak jak zostało tu przedstawione.
------
edit: przepraszam za spam - pisałem w trakcie gdy Qń wysłał swoje rozwiązanie - dziękuję ;]
------
edit: przepraszam za spam - pisałem w trakcie gdy Qń wysłał swoje rozwiązanie - dziękuję ;]