Ustawianie konkretnego ciągu

kitek2211 · Post autor: **kitek2211** » 24 sie 2012, o 15:39

Z góry przepraszam jeśli to zły dział, ale nie byłem pewien gdzie powinienem mój problem umieścić. Napisałem tu, bo podejrzewam, że jego rozwiązanie może być związane z teorią liczb i modulo.

Weźmy dowolną liczbę naturalną $\displaystyle{ N}$.
Chcemy stworzyć ciąg liczb naturalnych $\displaystyle{ a_n}$ dlugości $\displaystyle{ 2N^2}$, który ma następujące własności:
$\displaystyle{ \forall n\in \{1,2,\ldots ,2N^2\}, a_n\in \{1,2,\ldots 2N\}}$
oraz
$\displaystyle{ \forall k,l\in \{1,2,\ldots 2N\} \exists m: a_m=k\wedge (a_{m-1}=l\vee a_{m+1}=l)}$

Czyli chce stworzyć ciąg długości $\displaystyle{ 2N^2}$ taki, żeby każda liczba naturalna od $\displaystyle{ 1}$ do $\displaystyle{ 2N}$ "sąsiadowała" w którymś miejscu z każdą z pozostałych liczb z tego zakresu.

Z góry dziękuję za pomoc.

norwimaj · Post autor: **norwimaj** » 26 sie 2012, o 14:29

kitek2211 pisze: Czyli chce stworzyć ciąg długości $\displaystyle{ 2N^2}$ taki, żeby każda liczba naturalna od $\displaystyle{ 1}$ do $\displaystyle{ 2N}$ "sąsiadowała" w którymś miejscu z każdą z pozostałych liczb z tego zakresu.

Wyżej napisałeś nie że ma sąsiadować z każdą z pozostałych, tylko z każdą, ale tak się chyba nie da. Jeśli miało być $\displaystyle{ l\ne k}$, to się da. Na przykład dla $\displaystyle{ N=3}$:

$\displaystyle{ \begin{picture}(0,0)
\put(0,0){\line(0,-1){60}}
\put(0,-60){\line(1,0){60}}
\multiput(0,0)(10,-10){6}{\line(1,0){10}}
\multiput(10,0)(10,-10){6}{\line(0,-1){10}}
\multiput(5,-5)(10,-10){6}{\circle*{1}}
\multiput(5,-15)(10,-10){5}{\circle*{2}}
\multiput(5,-25)(10,-10){4}{\circle*{2}}
\multiput(5,-35)(10,-10){3}{\circle*{2}}
\multiput(5,-45)(10,-10){2}{\circle*{2}}
\multiput(5,-55)(10,-10){1}{\circle*{2}}
\multiput(5,-15)(10,-10){4}{\line(0,-1){10}}
\multiput(5,-35)(10,-10){2}{\line(0,-1){10}}
\multiput(5,-25)(10,-10){4}{\line(1,0){10}}
\multiput(5,-45)(10,-10){2}{\line(1,0){10}}
\put(-6,-8){$1$}
\put(-6,-58){$6$}
\put(3,-69){$1$}
\put(53,-69){$6$}
\end{picture}}$

Konstruujemy trzy ciągi, które w sumie mają długość $\displaystyle{ 18}$ i które w sumie spełniają żądany warunek: $\displaystyle{ 2132435465, 415263, 61}$.

Bez założenia $\displaystyle{ k\ne l}$ też mamy $\displaystyle{ N}$ takich ciągów, ale mają one w sumie długość $\displaystyle{ 2N^2+2N}$.

$\displaystyle{ \begin{picture}(0,0)
\put(0,0){\line(0,-1){60}}
\put(0,-60){\line(1,0){60}}
\multiput(0,0)(10,-10){6}{\line(1,0){10}}
\multiput(10,0)(10,-10){6}{\line(0,-1){10}}
\multiput(5,-5)(10,-10){6}{\circle*{2}}
\multiput(5,-15)(10,-10){5}{\circle*{2}}
\multiput(5,-25)(10,-10){4}{\circle*{2}}
\multiput(5,-35)(10,-10){3}{\circle*{2}}
\multiput(5,-45)(10,-10){2}{\circle*{2}}
\multiput(5,-55)(10,-10){1}{\circle*{2}}
\multiput(5,-5)(10,-10){5}{\line(0,-1){10}}
\multiput(5,-25)(10,-10){3}{\line(0,-1){10}}
\multiput(5,-45)(10,-10){1}{\line(0,-1){10}}
\multiput(5,-15)(10,-10){5}{\line(1,0){10}}
\multiput(5,-35)(10,-10){3}{\line(1,0){10}}
\multiput(5,-55)(10,-10){1}{\line(1,0){10}}
\put(-6,-8){$1$}
\put(-6,-58){$6$}
\put(3,-69){$1$}
\put(53,-69){$6$}
\end{picture}}$

kitek2211 · Post autor: **kitek2211** » 30 sie 2012, o 18:21

Oczywiście chodziło mi o przypadek$\displaystyle{ l \neq k}$ .
Potrzebuję rozwiązania tego problemu w ogólności dla dowolnego $\displaystyle{ N}$, nadal nie udało mi się tego rozpracować.
Dzięki za pomoc .

norwimaj · Post autor: **norwimaj** » 31 sie 2012, o 14:09

Widzisz, w jaki sposób rysunek wiąże się z otrzymanym ciągiem?