Interesantan zadatak

Pretpostavljam da hoćeš da kažeš „skup pozitivnih realnih brojeva“ umesto „pozitivan realan broj“.

Odgovor na postavljeno pitanje je da. Dokazaću ovo na dva načina, od kojih prvi pokazuje eksplicitnu konstrukciju traženih podskupa a drugi je tu samo zanimljivosti radi, jer se rešenje dobija u jednom koraku pozivanjem na specijalan slučaj jedne vrlo lepe (ali i vrlo teške) teoreme.

1) Prvi način:

Najpre ćemo podeliti skup $\textbf{N}$ na traženi način. Neka su definisani sledeći skupovi:
$A=\{3^{2i}l:i\in\textbf{N}_0,l\equiv 1\pmod 3\}$
$B=\{3^{2i}l:i\in\textbf{N}_0,l\equiv -1\pmod 3\}$
$C=\{3^{2i-1}l:i\in\textbf{N},l\equiv 1\pmod 3\}$
$D=\{3^{2i-1}l:i\in\textbf{N},l\equiv -1\pmod 3\}$

Dokazaćemo da ovi skupovi zadovoljavaju uslove zadatka. Pretpostavimo da postoje $a,b,c\in A$ za koje važi $2a+2b=3c$ . Imamo sledeće:
$2\cdot 3^{2i}l_1+2\cdot 3^{2j}l_2=3^{2k+1}l_3$
Neka je $i\leq j$ .
Ukoliko je $i\leq k$ deleći sve sa $3^{2i}$ imamo:
$2l_1+2\cdot 3^{2j-2i}l_2=3^{2k-2i+1}l_3$
Pošto je desna strana deljiva sa $3$ , mora biti $i=j$ . Tada važi:
$2l_1+2l_2=3^{2k-2i+1}l_3$
S druge strane, kako je $l_1\equiv l_2\equiv 1\pmod 3$ sledi da leva strana nikad ne može biti deljiva sa $3$ . Kontradikcija.
Još lakše, ukoliko je $k<i$ , deleći sve sa $3^{2k+1}$ imamo:
$2\cdot 3^{2i-2k-1}l_1+2\cdot 3^{2j-2k-1}=l_3$
pa je leva strana deljiva sa $3$ a desna nije.

Analogno se pokazuje da data jednačina nije rešiva ni u ostalim podskupima.

Za $x\in\textbf{R}^+$ koristićemo oznake $x=\lfloor x\rfloor+\{x\}=\lceil x\rceil-\}x\{$ , gde su sa $\lfloor\cdot\rfloor$ i $\lceil\cdot\rceil$ standardno označeni donji i gornji ceo deo, redom. Za $K\in\{A,B,C,D\}$ i $1\leq i\leq 3$ označimo:
$\mathop{K}_i=\left\{x:\lfloor x\rfloor\in K,\frac{i-1}3\leq\{x\}<\frac i 4\right\}$
$\mathop{K}^i=\left\{x:\lceil x\rceil\in K,\frac{i-1}3<\}x\{<\frac i 4\right\}$

Potrebna su nam još dva skupa, naime:
$Q_0=\left\{n+\frac 1 2:n\in\textbf{N}_0\right\}$
$Q_1=\left\{n+\frac 1 4,n+\frac 3 4:n\in\textbf{N}_0\right\}$

Lako se proverava da su svi ovi skupovi međusobno disjunktni i da je $\mathop{\bigcup_{K\in\{A,B,C,D\}}}_{1\leq i\leq 3}\left(\mathop{K}_i\cup\mathop{K}^i\right)\cup Q_0\cup Q_1=\textbf{R}^+$ . Preostaje još da se dokaže da jednačina $2a+2b=3c$ nije rešiva ni u jednom od njih.

Neka $a,b,c\in\mathop{K}_i$ i pretpostavimo da važi $2a+2b=3c$ . Tada:
$2(\lfloor a\rfloor+\{a\})+2(\lfloor b\rfloor+\{b\})=3(\lfloor c\rfloor+\{c\})$
$2\lfloor a\rfloor+2\lfloor b\rfloor+2(\{a\}+\{b\})=3\lfloor c\rfloor+3\{c\}$
Iz ograničenja sledi $i-1<\frac{4(i-1)}3\leq 2(\{a\}+\{b\})<i$ i $i-1\leq 3\{c\}<\frac{3i}4<i$ , odakle zaključujemo da mora važiti $\lfloor2\lfloor a\rfloor+2\lfloor b\rfloor+2(\{a\}+\{b\})\rfloor=2\lfloor a\rfloor+2\lfloor b\rfloor+i-1$ i $\lfloor3\lfloor c\rfloor +3\{c\}\rfloor=3\lfloor c\rfloor+i-1$ pa je $2\lfloor a\rfloor+2\lfloor b\rfloor=3\lfloor c\rfloor$ što je nemoguće na osnovu već dokazanog jer $\lfloor a\rfloor,\lfloor b\rfloor,\lfloor c\rfloor\in K$ .

Slično, ako $a,b,c\in\mathop{K}^i$ i $2a+2b=3c$ onda imamo:

$2(\lceil a\rceil-\}a\{)+2(\lceil b\rceil-\}b\{)=3(\lceil c\rceil-\}c\{)$
$2\lceil a\rceil+2\lceil b\rceil-2(\}a\{+\}b\{)=3\lceil c\rceil-3\}c\{$
Pošto je $i-1<\frac{4(i-1)}3<2(\{a\}+\{b\})<i$ i $i-1<3\{c\}<\frac{3i}4<i$ sledi $\lceil 2\lceil a\rceil+2\lceil b\rceil-2(\}a\{+\}b\{)\rceil=2\lceil a\rceil+2\lceil b\rceil-(i-1)$ i $\lceil 3\lceil c\rceil-3\}c\{\rceil=3\lceil c\rceil-(i-1)$ , odnosno $2\lceil a\rceil+2\lceil b\rceil=3\lceil c\rceil$ što je nemoguće, slično malopređašnjem objašnjenju.

I poslednje, ako $a,b,c\in Q_i$ onda je leva strana jednakosti ceo broj a desna nije, pa jednačina nema rešenja ni u ovom skupu.

Za kraj samo da napomenem da, kao što se može prebrojati, ovo rešenje uključuje $26$ podskupa. Ovo nikako nije minimum, štaviše relativno jednostavnom modifikacijom ovo rešenje možemo svesti na $16$ podskupa, ali sam se odlučio za ovo jer je prirodnije a broj podskupa ne igra veliku ulogu.

2) Drugi način:

Definicija 1:

Neka $u,v\in\textbf{N}$ i neka je $A$ matrica $u\times v$ sa elementima iz $\textbf{Q}$ . Neka je $S$ potpolugrupa od $(\textbf{R},+)$ . Tada kažemo da za $A$ važi $KPR/S$ (kernel partition regular over $S$ ) akko kad god je $S\setminus\{0\}$ obojen sa konačno mnogo boja postoji monohromatski $\overrightarrow{x}\in S^v$ takav da je $A\overrightarrow{x}=\overrightarrow{0}$ .

Definicija 2:

Neka $u,v\in\textbf{N}$ i neka je $A$ matrica $u\times v$ sa elementima iz $\textbf{Q}$ . Označimo kolone od $A$ sa $\overrightarrow{c_1},\overrightarrow{c_2},\dots,\overrightarrow{c_v}$ . Tada $A$ zadovoljana uslov kolona akko postoji $m\in\{1,2,\dots,v\}$ i particija $\{I_1,I_2,\dots,I_m\}$ skupa $\{1,2,\dots,v\}$ u neprazne podskupe takva da važi:
a) $\sum_{i\in I_1}\overrightarrow{c_i}=\overrightarrow{0}$ ;
b) za svako $t\in\{2,3,\dots,m\}$ , $\sum_{i\in I_t}\overrightarrow{c_i}$ je linearna kombinacija sa koeficijentima iz $\textbf{Q}$ vektora iz $\left\{\overrightarrow{c_i}:i\in\bigcup_{j=1}^{t-1}I_j\right\}$ .

Teorema: (Rado)

Neka $u,v\in\textbf{N}$ i neka je $A$ matrica $u\times v$ sa elementima iz $\textbf{Q}$ . Sledeći iskazi su ekvivalentni:
a) $A$ je $KPR/\textbf{N}$ ;
b) $A$ je $KPR/\textbf{Z}$ ;
c) $A$ je $KPR/\textbf{Q}^+$ ;
d) $A$ je $KPR/\textbf{Q}$ ;
e) $A$ je $KPR/\textbf{R}^+$ ;
f) $A$ je $KPR/\textbf{R}$ ;
g) $A$ zadovoljava uslov kolona.

Primenom ove teoreme rešenje zadatka dobijamo u jednom koraku. Zaista, neka je
$A=[2\quad 2\quad -3]$
Nemoguće je zadovoljiti uslov a) iz Definicije 2, pa sledi da $A$ ne zadovoljava uslov kolona, pa iz Teoreme dobijamo da nije $KPR/\textbf{R}^+$ , što je ekvivalentno pitanju iz zadatka.

Da vidimo još neke zanimljive posledice Radove teoreme.

Šurova teorema:

Za svako bojenje skupa $\textbf{N}$ u konačno mnogo boja postoje $x,y\in\mathbf{N}$ takvi da su $x,y,x+y$ iste boje.

Dokaz:

Primenimo Radovu teoremu na matricu $A=[1\quad 1\quad -1]$ koja zadovoljava uslov kolona.

Van der Waerden's Theorem:

Za svako bojenje skupa $\textbf{N}$ u konačno mnogo boja postoji konačna monohromatska aritmetička progresija proizvoljno velike dužine.

Dokaz:

Pretpostavimo da želimo da pokažemo da postoji aritmetička progresija dužine $5$ (slično ide za bilo koju dužinu). Neka je $y_i=a+(i-1)d$ za $1\leq i\leq 5$ . Tada od sistema jednačina:
$y_1-2y_2+y_3=0$
$y_2-2y_3+y_4=0$
$y_3-2y_4+y_5=0$
pravimo sledeću matricu:
$A=\left[\begin{array}{ccccc} 1&-2&1&0&0\\ 0&1&-2&1&0\\ 0&0&1&-2&1\end{array}\right]$
Zbir svih kolona ove matrice je $\overrightarrow{0}$ pa ona zadovoljava uslov kolona. Ipak, život nam nije tako lep pošto sve što nam Radova teorema garantuje u ovom slučaju je da postoji aritmetička progresija makar sa $d=0$ , što nije ono što nas zanima. Ovo se da lako popraviti, naime možemo staviti $y_6=d$ i tražiti da i ono bude iste boje iz jednačine
$y_1-y_2+y_6=0$
Tada je
$A=\left[\begin{array}{cccccc} 1&-2&1&0&0&0\\ 0&1&-2&1&0&0\\ 0&0&1&-2&1&0\\ 1&-1&0&0&0&1\end{array}\right]$
koja zadovoljava uslov kolona kad uzmemo $I_1=\{1,2,3,4,5\}$ i $I_2=\{6\}$ .

Literatura:

[1] R. Rado, Studien zur Kombinatorik, Math. Zeit. 36 (1933), 242-280.
[2] R. Rado, Note on combinatorial analysis, Proc. London Math. Soc. 48 (1943), 122-160.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Forum kao aplikacija na telefonu

Srodne teme