Re: [MIX] Suplement KMDO
: 16 lis 2024, o 11:42
Choć wydaje mi się, że równanie (*) musi zawierać dla niektórych \(\displaystyle{ k}\) sprzeczność bo w przypadku gdy:
\(\displaystyle{ r_{1}+r_{4} \neq n}\) to i tak dla niektórych k (niektóre równania) z układu równań z zadania są spełnione a dla niektórych nie...
przypadek:
\(\displaystyle{ \varepsilon-r_{1}=0}\)
implikowałby:
\(\displaystyle{ r_{4}=n}\)
co jest wykluczone z uwagi na definicję reszty
co do zadania 55 oczywiście to obserwacje, którą należałoby pociągnąć np. indukcją z uwagi na 6 przypadków:
pierwsza jedynka jak i druga oraz dwie minusjedynki występują co sześć tak samo jak dwójka i minusdwójka,,,
np.dla pierwszej minusjedynki można iść indukcją po:
\(\displaystyle{ n=6k-4}\) , podobnie jak i pozostałych...
Inny pomysł na zadanie 199:
to znaczy pomysł od pewnego momentu bo doszliśmy dotąd:
(*) \(\displaystyle{ \left\lfloor k\frac{r_{1}}{n} \right\rfloor +\left\lfloor k\frac{r_{2}}{n} \right\rfloor+\left\lfloor k\frac{r_{3}}{n} \right\rfloor+\left\lfloor k\frac{r_{4}}{n} \right\rfloor=2k-2 , k=1,2,3,...,k-1}\)
wiadomo też co wykazałem zachodzi:
\(\displaystyle{ r_{1}+r_{2}+r_{3}+r_{4}=2n}\)
z tego:
\(\displaystyle{ r_{4}=2n-\left( r_{1}+r_{2}+r_{3}\right) }\)
po podstawieniu do (*) otrzymamy:
\(\displaystyle{ \left\lfloor k\frac{r_{1}}{n} \right\rfloor +\left\lfloor k\frac{r_{2}}{n} \right\rfloor+\left\lfloor k\frac{r_{3}}{n} \right\rfloor= \left\lfloor k\frac{r_{1}+r_{2}+r_{3}}{n} \right\rfloor-1 }\)
jakby teraz podstawić:
\(\displaystyle{ x,y,x= k\frac{r_{i}}{n}}\)
otrzymamy równanie:
\(\displaystyle{ \left\lfloor x \right\rfloor + \left\lfloor y \right\rfloor + \left\lfloor z \right\rfloor= \left\lfloor x+y+z \right\rfloor-1}\)
zmienne są dodatnie, więc powyższe równanie można wydedukować, jest równoważne podwójnej nierówności na częściach ułamkowych:
\(\displaystyle{ 1 \le \left\{ x\right\} +\left\{ y\right\} +\left\{ z\right\} <2 }\)
albo:
\(\displaystyle{ 1 \le \left\{ k\frac{r_{1}}{n}\right\}+\left\{ k\frac{r_{2}}{n}\right\}+\left\{ k\frac{r_{1}}{n}\right\} <2 }\)
i teraz skoro wiemy, że:
\(\displaystyle{ (r_{i},n)=1 NWD}\)
to skoro tak jest, znaczy, że:
\(\displaystyle{ kr_{i}, k=1,2,3,...,n-1}\)
generuje wszystkie reszty modulo \(\displaystyle{ n}\) od jeden do \(\displaystyle{ n-1}\) oczywiście niekoniecznie po kolei czyli mamy tu pewną permutację wszystkich reszt
załóżmy teraz, że żadna suma:
\(\displaystyle{ r_{i}+r_{j} \neq n , i \neq j}\)
zakładając, że np:
dla pewnych: \(\displaystyle{ i, j}\)
\(\displaystyle{ r_{i}+r_{j}>n}\)
możemy zapisać:
dla ustalenia uwagi załóżmy, że:
\(\displaystyle{ r_{1}+r_{2}>n}\)
wtedy połóżmy:
\(\displaystyle{ r_{1}+r_{2}=n+r}\)
czeli mamy takie reszty:
\(\displaystyle{ kn, kr, kr_{3} , k=1,2,...,n-1}\)
jak widać suma:
\(\displaystyle{ kr+kr_{3}}\) - powinna być zawsze mniesza od \(\displaystyle{ n}\), ale \(\displaystyle{ kr_{3}}\) to permutacja wszystkich reszt \(\displaystyle{ n}\) a reszta \(\displaystyle{ kr}\) jest niezerowa, więc w najgorszym wypadku wyniesie jeden i suma ta może wynieść w najgorszym czyli najmniejszym przypadku:
\(\displaystyle{ 1+n-1=n=n}\) co daje sprzeczność...
oczywiście może się zdarzyć, że suma:
\(\displaystyle{ r_{i}+r_{j}<n}\) dla wszystkich przypadków , ale na pewno znajdziemy takie \(\displaystyle{ k}\) , ale założymy, że:
\(\displaystyle{ (k,n)=1}\)
i otrzymamy układ reszt:
\(\displaystyle{ kr_{1} , kr_{2}, kr_{3} , (kr_{i},n)=1}\)
tak możemy dobrać i permutować, że:
\(\displaystyle{ kr_{1} + kr_{2}>n}\)
i wrócimy do sytuacji poprzedniej...
może się też zdarzyć, że:
\(\displaystyle{ r_{1}+r_{2}+r_{3}<n}\), ale ten przypadek na wstępie nie spełnia warunku zadania...
może i cos przeoczyłem ,ale teraz spróbujmy w druga stronę załóżmy, że istnieją takie reszty, np.: \(\displaystyle{ r_{1}, r_{2}}\) , że:
\(\displaystyle{ r_{1}+r_{2}=n}\)
wtedy też układ reszt:
\(\displaystyle{ kr_{1}+kr_{2}=n}\)
więc skoro:
\(\displaystyle{ r_{3} <n}\) więc mamy tezę...
podsumowując gdy zachodzi sytuacja, że dla wszystkich: \(\displaystyle{ i \neq j}\)
\(\displaystyle{ r_{i}+r_{j} \neq n}\)
to mogą istnieć takie \(\displaystyle{ k}\) , że:
\(\displaystyle{ \left\lfloor k\frac{r_{1}}{n} \right\rfloor +\left\lfloor k\frac{r_{2}}{n} \right\rfloor+\left\lfloor k\frac{r_{3}}{n} \right\rfloor+\left\lfloor k\frac{r_{4}}{n} \right\rfloor=2k-2 }\)
ale zawsze się znajdzie takie \(\displaystyle{ k}\) , że to równanie nie będzie spełnione...
bez założenia:
\(\displaystyle{ (r_{i},n)=1}\)
też byśmy nic nie wskórali bo dzięki temu mamy i to, że suma reszt daje \(\displaystyle{ 2n}\) , oraz, że mamy możliwość generowania wszystkich reszt...
\(\displaystyle{ r_{1}+r_{4} \neq n}\) to i tak dla niektórych k (niektóre równania) z układu równań z zadania są spełnione a dla niektórych nie...
przypadek:
\(\displaystyle{ \varepsilon-r_{1}=0}\)
implikowałby:
\(\displaystyle{ r_{4}=n}\)
co jest wykluczone z uwagi na definicję reszty
co do zadania 55 oczywiście to obserwacje, którą należałoby pociągnąć np. indukcją z uwagi na 6 przypadków:
pierwsza jedynka jak i druga oraz dwie minusjedynki występują co sześć tak samo jak dwójka i minusdwójka,,,
np.dla pierwszej minusjedynki można iść indukcją po:
\(\displaystyle{ n=6k-4}\) , podobnie jak i pozostałych...
Inny pomysł na zadanie 199:
to znaczy pomysł od pewnego momentu bo doszliśmy dotąd:
(*) \(\displaystyle{ \left\lfloor k\frac{r_{1}}{n} \right\rfloor +\left\lfloor k\frac{r_{2}}{n} \right\rfloor+\left\lfloor k\frac{r_{3}}{n} \right\rfloor+\left\lfloor k\frac{r_{4}}{n} \right\rfloor=2k-2 , k=1,2,3,...,k-1}\)
wiadomo też co wykazałem zachodzi:
\(\displaystyle{ r_{1}+r_{2}+r_{3}+r_{4}=2n}\)
z tego:
\(\displaystyle{ r_{4}=2n-\left( r_{1}+r_{2}+r_{3}\right) }\)
po podstawieniu do (*) otrzymamy:
\(\displaystyle{ \left\lfloor k\frac{r_{1}}{n} \right\rfloor +\left\lfloor k\frac{r_{2}}{n} \right\rfloor+\left\lfloor k\frac{r_{3}}{n} \right\rfloor= \left\lfloor k\frac{r_{1}+r_{2}+r_{3}}{n} \right\rfloor-1 }\)
jakby teraz podstawić:
\(\displaystyle{ x,y,x= k\frac{r_{i}}{n}}\)
otrzymamy równanie:
\(\displaystyle{ \left\lfloor x \right\rfloor + \left\lfloor y \right\rfloor + \left\lfloor z \right\rfloor= \left\lfloor x+y+z \right\rfloor-1}\)
zmienne są dodatnie, więc powyższe równanie można wydedukować, jest równoważne podwójnej nierówności na częściach ułamkowych:
\(\displaystyle{ 1 \le \left\{ x\right\} +\left\{ y\right\} +\left\{ z\right\} <2 }\)
albo:
\(\displaystyle{ 1 \le \left\{ k\frac{r_{1}}{n}\right\}+\left\{ k\frac{r_{2}}{n}\right\}+\left\{ k\frac{r_{1}}{n}\right\} <2 }\)
i teraz skoro wiemy, że:
\(\displaystyle{ (r_{i},n)=1 NWD}\)
to skoro tak jest, znaczy, że:
\(\displaystyle{ kr_{i}, k=1,2,3,...,n-1}\)
generuje wszystkie reszty modulo \(\displaystyle{ n}\) od jeden do \(\displaystyle{ n-1}\) oczywiście niekoniecznie po kolei czyli mamy tu pewną permutację wszystkich reszt
załóżmy teraz, że żadna suma:
\(\displaystyle{ r_{i}+r_{j} \neq n , i \neq j}\)
zakładając, że np:
dla pewnych: \(\displaystyle{ i, j}\)
\(\displaystyle{ r_{i}+r_{j}>n}\)
możemy zapisać:
dla ustalenia uwagi załóżmy, że:
\(\displaystyle{ r_{1}+r_{2}>n}\)
wtedy połóżmy:
\(\displaystyle{ r_{1}+r_{2}=n+r}\)
czeli mamy takie reszty:
\(\displaystyle{ kn, kr, kr_{3} , k=1,2,...,n-1}\)
jak widać suma:
\(\displaystyle{ kr+kr_{3}}\) - powinna być zawsze mniesza od \(\displaystyle{ n}\), ale \(\displaystyle{ kr_{3}}\) to permutacja wszystkich reszt \(\displaystyle{ n}\) a reszta \(\displaystyle{ kr}\) jest niezerowa, więc w najgorszym wypadku wyniesie jeden i suma ta może wynieść w najgorszym czyli najmniejszym przypadku:
\(\displaystyle{ 1+n-1=n=n}\) co daje sprzeczność...
oczywiście może się zdarzyć, że suma:
\(\displaystyle{ r_{i}+r_{j}<n}\) dla wszystkich przypadków , ale na pewno znajdziemy takie \(\displaystyle{ k}\) , ale założymy, że:
\(\displaystyle{ (k,n)=1}\)
i otrzymamy układ reszt:
\(\displaystyle{ kr_{1} , kr_{2}, kr_{3} , (kr_{i},n)=1}\)
tak możemy dobrać i permutować, że:
\(\displaystyle{ kr_{1} + kr_{2}>n}\)
i wrócimy do sytuacji poprzedniej...
może się też zdarzyć, że:
\(\displaystyle{ r_{1}+r_{2}+r_{3}<n}\), ale ten przypadek na wstępie nie spełnia warunku zadania...
może i cos przeoczyłem ,ale teraz spróbujmy w druga stronę załóżmy, że istnieją takie reszty, np.: \(\displaystyle{ r_{1}, r_{2}}\) , że:
\(\displaystyle{ r_{1}+r_{2}=n}\)
wtedy też układ reszt:
\(\displaystyle{ kr_{1}+kr_{2}=n}\)
więc skoro:
\(\displaystyle{ r_{3} <n}\) więc mamy tezę...
podsumowując gdy zachodzi sytuacja, że dla wszystkich: \(\displaystyle{ i \neq j}\)
\(\displaystyle{ r_{i}+r_{j} \neq n}\)
to mogą istnieć takie \(\displaystyle{ k}\) , że:
\(\displaystyle{ \left\lfloor k\frac{r_{1}}{n} \right\rfloor +\left\lfloor k\frac{r_{2}}{n} \right\rfloor+\left\lfloor k\frac{r_{3}}{n} \right\rfloor+\left\lfloor k\frac{r_{4}}{n} \right\rfloor=2k-2 }\)
ale zawsze się znajdzie takie \(\displaystyle{ k}\) , że to równanie nie będzie spełnione...
bez założenia:
\(\displaystyle{ (r_{i},n)=1}\)
też byśmy nic nie wskórali bo dzięki temu mamy i to, że suma reszt daje \(\displaystyle{ 2n}\) , oraz, że mamy możliwość generowania wszystkich reszt...
