układ z mod

rochaj · Post autor: **rochaj** » 26 lip 2014, o 10:38

Niech n będzie liczbą naturalną $\displaystyle{ (n\ge 6)}$.
Ile trójek $\displaystyle{ (a,b,c)}$ liczb całkowitych spełnia ten układ
$\displaystyle{ \begin{cases}a+b+c\equiv 0\pmod n\\ 1\le a<b<c\le n \end{cases}\quad?}$

Hydra147 · Post autor: **Hydra147** » 26 lip 2014, o 13:30

Skoro $\displaystyle{ a<b<c \le n}$, to $\displaystyle{ a+b+c<3n}$ czyli $\displaystyle{ a+b+c=n}$, lub $\displaystyle{ a+b+c=2n}$.
Wiadomo, że równanie:
$\displaystyle{ x_{1} + x_{2} + x_{3} =m-3}$ ma $\displaystyle{ {m-1\choose 2}}$ rozwiązań w liczbach całkowitych nieujemnych, czyli równanie $\displaystyle{ x_{1} + x_{2} + x_{3} =m}$ ma $\displaystyle{ {m-1\choose 2}}$ rozwiązań w liczbach całkowitych dodatnich. Sprawdźmy ile jest sytuacji, w których $\displaystyle{ x_{1} = x_{2}}$. Mamy wówczas równanie $\displaystyle{ 2 x_{1}+ x_{3}=m}$. Dla każdego $\displaystyle{ x_{1} \in \left\{ 1,2,...,\left[ \frac{m-1}{2} \right] \right\}}$ istnieje $\displaystyle{ x_{2}}$ spełniające powyższe równanie i jest wyznaczone w sposób jednoznaczny. Jest ich zatem $\displaystyle{ \left[ \frac{m-1}{2} \right]}$. Ale może też zachodzić $\displaystyle{ x_{2} = x_{3}}$ oraz $\displaystyle{ x_{1} = x_{3}}$ czyli razem mamy $\displaystyle{ 3\left[ \frac{m-1}{2} \right]}$ możliwości. Natomiast jeżeli $\displaystyle{ m}$ jest podzielne przez $\displaystyle{ 3}$, to przypadek $\displaystyle{ x_{1} = x_{2} = x_{3}}$ policzyliśmy $\displaystyle{ 3}$ razy czyli o $\displaystyle{ 2}$ za dużo. Ponadto, jeśli kolejność jest istotna (a jest, gydż $\displaystyle{ a<b<c}$) to wynik musimy podzielić przez liczbę permutacji czyli $\displaystyle{ 6}$. Niech $\displaystyle{ f(n)}$ będzie szukaną liczbą trójek. Korzystając z powyższych własności wyprowadzamy:
$\displaystyle{ f(n)= \frac{5n^2-18n+g(n)}{12}}$
gdzie $\displaystyle{ g(n)}$ to funkcja określona następująco:
$\displaystyle{ g(n)= \begin{cases} 24 &\text{dla } n\equiv 0 \pmod{6} \\ 13 &\text{dla } n\equiv \pm 1 \pmod{6} \\ 16 &\text{dla } n\equiv \pm 2 \pmod{6} \\ 21 &\text{dla } n\equiv 3 \pmod{6} \end{cases}}$
Co kończy rozwiązanie zadania.

-- 26 lip 2014, o 12:59 --

Wyliczyłem (mechanicznie jak i za pomocą wzoru), że $\displaystyle{ f(6)=8; f(7)=11; f(8)=16; f(9)=22}$, wiec wzór chyba jest dobry. Dodatkowo zauważmy, że:
$\displaystyle{ f(n)= \frac{5n^2-18n+g(n)}{12}= \frac{5n^2-18n+12}{12} + \frac{g(n)-12}{12}}$. Skoro $\displaystyle{ \frac{g(n)-12}{12} \in \left\langle 0;1 \right\rangle}$, a $\displaystyle{ f(n)}$ jest zawsze całkowite, to możemy po prostu zapisać $\displaystyle{ f(n)= \left[ \frac{5n^2-18n}{12}\right] +2}$.

-- 26 lip 2014, o 15:08 --

Trzeba wnieść kolejne poprawki, gdyż moje rozwiązanie zakłada możliwość $\displaystyle{ c>n}$. Policzymy teraz ile jest takich trójek. Oto ich lista:
$\displaystyle{ (2n-3,2,1),(2n-4,3,1),(2n-5,4,1),(2n-5,3,2),(2n-6,5,1),(2n-6,4,2)...}$
Jest tylko $\displaystyle{ 1}$ trójka, w której $\displaystyle{ c=2n-3,2n-4}$ ale już $\displaystyle{ 2}$, w których $\displaystyle{ c=2n-5,2n-6}$.Widzimy zatem, że jeżeli $\displaystyle{ n}$ jest parzyste, to musimy odjąć $\displaystyle{ 1+1+2+2+...+ (\frac{n}{2}-2) + (\frac{n}{2}-2)+(\frac{n}{2}-1)= \frac{n^2-4n+4}{4}}$. Analogowo rozumujemy dla $\displaystyle{ n}$ nieparzystego dostając do odjęcia $\displaystyle{ 1+1+2+2+...+ \frac{n-3}{2} + \frac{n-3}{2}= \frac{n^2-4n+3}{4}}$. Dostajemy zatem nową funkcję $\displaystyle{ f}$:
$\displaystyle{ f(n)= \begin{cases} \frac{n^2-3n+6}{6} &\text{gdy } 3|n \\ \frac{n^2-3n+2}{6} &\text{w przeciwnym wypadku } \end{cases}}$.
Łatwo zauważyć, że funkcja $\displaystyle{ f}$ daje się również przedstawić w postaci $\displaystyle{ f(n)=$\left\lceil\dfrac{(n-1)(n-2)}{6}\right\rceil$}$. Istotnie, gdy $\displaystyle{ n=3k}$, to zachodzi
$\displaystyle{ $\left\lceil\dfrac{(3k-1)(3k-2)}{6}\right\rceil$=$\left\lceil 3 \frac{k(k-1)}{2}+ \frac{1}{3} \right\rceil$= \dfrac{3k(k-1)}{2}+1= \frac{(3k)^2-3(3k)+6}{6}}$ , zaś gdy $\displaystyle{ n}$ jest niepodzielne przez $\displaystyle{ 3}$, to zachodzi po prostu równość $\displaystyle{ $\left\lceil\dfrac{(n-1)(n-2)}{6}\right\rceil$=\dfrac{(n-1)(n-2)}{6}=\frac{n^2-3n+2}{6}}$.

robertm19 · Post autor: **robertm19** » 27 lip 2014, o 11:13

A ten przypadek $\displaystyle{ a+b+c=2n}$ uwzględniłeś?
Powstanie tych funkcji też jest nie jasne.
A co z $\displaystyle{ a,b>n}$?

Hydra147 · Post autor: **Hydra147** » 27 lip 2014, o 12:49

Tak przypadek $\displaystyle{ a+b+c=2n}$ uwzględniłem. Dodaję do tego liczbę trójek z przypadku $\displaystyle{ a+b+c=n}$, a odejmuję liczbę trójek, w których $\displaystyle{ c>n}$. A skoro $\displaystyle{ a<b<c}$, to na pewno $\displaystyle{ a,b<n}$. Jeśli masz jakieś pytania odnośnie konkretnych przejść, za półtorej godzinki postaram się na nie odpowiedzieć. Wynik jest dobry, bo zgadza się z odpowiedzią Rochaja.

robertm19 · Post autor: **robertm19** » 27 lip 2014, o 13:52

Ok, jestem ciekaw.

Hydra147 · Post autor: **Hydra147** » 27 lip 2014, o 15:02

Ok, już jestem. Napisz mi, których przejść konkretnie nie rozumiesz, to Ci je wyjaśnię.

robertm19 · Post autor: **robertm19** » 27 lip 2014, o 15:27

No pokaż jak tą funkcję konstruujesz.

Hydra147 · Post autor: **Hydra147** » 27 lip 2014, o 16:00

Zakładam, że wszystko do momentu użycia przeze mnie poraz pierwszy symbolu $\displaystyle{ f}$ rozumiesz.
Rozbiłem problem ogólny na $\displaystyle{ 4}$ przypadki. $\displaystyle{ 3|n \wedge 2|n}$; $\displaystyle{ 3 \! \not | \; n \wedge 2 \! \not | \; n}$; $\displaystyle{ 2|n \wedge 3 \! \not | \; n}$; $\displaystyle{ 2 \! \not | \; n \wedge 3|n}$. Zauważ, że odpowiadają one (odpowiednio) przystawaniom do $\displaystyle{ 0, \pm 1, \pm 2, 3}$ modulo $\displaystyle{ 6}$. Co musimy zrobić aby uzyskać wynik:
1. Obliczyć ile jest trójek liczb całkowitych dodatnich $\displaystyle{ a,b,c}$ spełniających $\displaystyle{ a+b+c=n}$ oraz $\displaystyle{ a+b+c=2n}$ (jest ich odpowiednio $\displaystyle{ {n-1\choose 2}}$ oraz $\displaystyle{ {2n-1\choose 2}}$).
2. Odjąć od tej liczby ilość rozwiązań w których co najmniej $\displaystyle{ 2}$ zmienne są sobie równe (musimy zatem odjąć $\displaystyle{ 3\left[ \frac{n-1}{2} \right] + 3\left[ \frac{2n-1}{2} \right])}$. I tu pojawia się różnicowanie na parzyste i nieparzyste. Jeśli bowiem $\displaystyle{ n}$ nieparzyste, to musimy odjąć $\displaystyle{ \frac{9n-9}{2}}$, a gdy parzyste to $\displaystyle{ \frac{9n-12}{2}}$.
3. Jeżeli $\displaystyle{ 3|n}$, to może zajść także $\displaystyle{ a=b=c}$. Przypadek ten w podpunkcie $\displaystyle{ 2.}$ odjęliśmy trzykrotnie, musimy zatem teraz dodać dwójkę (jeśli $\displaystyle{ 3|n}$). Robi się więc podział na podzielne i niepodzielne przez $\displaystyle{ 3}$.
4. To co otrzymaliśmy do tej pory to ilość trójek $\displaystyle{ (a,b,c)}$ dodatnich liczb całkowitych takich, że $\displaystyle{ a \neq b \neq c \neq a}$ oraz $\displaystyle{ a+b+c=n}$ lub$\displaystyle{ a+b+c=2n}$. My chcemy jednak, by $\displaystyle{ c>b>a}$. Otrzymany wynik musimy więc podzielić przez liczbę permutacji zbioru $\displaystyle{ 3}$-elementowego czyli $\displaystyle{ 6}$.
5.Tak otrzymany wynik prowadzi nas do tej pierwszej funkcji $\displaystyle{ f}$ lecz nie jest ona poprawna, gdyż może się zdarzyć, że $\displaystyle{ c>n}$. To ile jest takich trójek (w zależności od parzystości $\displaystyle{ n}$) liczyłem już w poprzednim poście.
Widzimy, że dla $\displaystyle{ n}$ parzystych i $\displaystyle{ n}$ nieparzystych otrzymujemy taki sam wynik. Znaczenie ma tylko podzielność przez $\displaystyle{ 3}$. Prowadzi nas to do tej drugiej definicji funkcji $\displaystyle{ f}$. Jest ona poprawna ale trochę zbyt skomplikowana. Za pomocą przekształceń wyprowadzamy wzór $\displaystyle{ f(n)=$\left\lceil\dfrac{(n-1)(n-2)}{6}\right\rceil$}$, który jest ładny, miły i przyjemny .

robertm19 · Post autor: **robertm19** » 27 lip 2014, o 16:11

Chwileczke, skąd założenie o rozbiciu na takie 4 przypadki?

Hydra147 · Post autor: **Hydra147** » 27 lip 2014, o 16:16

Chodzi o to, że w zależności od parzystości $\displaystyle{ n}$ liczba, jaką odejmujemy w podpunkcie 2. jest inna, a od podzielności przez $\displaystyle{ 3}$ zależy czy w podpunkcie 3. dodamy tę dwójkę czy nie. Niepotrzebnie napisałem o tym rozbiciu na $\displaystyle{ 4}$ przypadki na samym początku. Z resztą później i tak zwija się to do dwóch, gdyż niezależnie od parzystości $\displaystyle{ n}$ otrzymujemy te same wyniki.