سوال نظریه از نوع hard

حالا هرکی · 1391/1/28

سوال( تویمادا یاکوت)
میدانیم

$\alpha$

،عددی حقیقی است ثابت کنید بینهایت عدد طبیعی

$n$

وجود دارد که

$\left \lfloor n^{2} \alpha \right \rfloor$

عددی زوج شود .

threehandsnal · 1391/1/28

پاسخ : سوال نظریه از نوع hard

حالا هرکی گفت

ابتدا تعریف می کنیم:

$\overline{a_na_{n-1}...a_1a_0,b_1b_2...b_m}_{(2)}=a_n\times 2^n+a_{n-1}\times 2^{n-1}+...+a_1\times 2^1+a_0\times 2^0+b_1\times 2^{-1}+b_2\times 2^{-2}+...+b_m\times {2^{-m}}$

همچنین قرار دهید

$P(n)=\left \lfloor n^2\alpha \right \rfloor$

.
*فرض کنید آلفا گویا باشه و به صورت

$\alpha =\frac{p}{q}$

باشه. اونموقع

$\forall n\in \mathbb{N}:P(2^nq)\in Even\:Numbers$

پس نامتناهی تا

$n$

پیدا شد که

$P(n)$

عددی زوج بشه!

*حالا فرض کنید آلفا گنگ باشه.و همچنین فرض کنید متناهی تا

$P(n)$

داشته باشیم که زوج باشه!میایم آلفا رو در مبنای

$2$

(به صورت نامتناهی از طرف راست) مینویسیم:

$a_i,b_i\in \left \{ 0,1 \right \}:\alpha =\overline{a_ma_{m-1}...a_1a_0/b_1...}_{(2)}$

اگه تعداد

$b_{2k+1}=0$

ها نامتناهی باشه اونموقع میتونیم

$n=2^{k+1}$

قرار بدیم و بینهایت عدد زوج بگیریم که تناقضه! پس از یه

$b_i$

ای به بعد همه

$b_{odd}$

ها برابر

$1$

هستند! حالا یه

$n$

رو در نظر بگیرید که

$n>\frac{i}{2}$

. واضحه که

$P(2^n),P(3.2^n)$

هر دو فرد هستند.

$2^{2n}\alpha \equiv \overline{1/k_11k_21k_31...}_{(2)}\:(mod\:2)$

بنابراین:

$P(3.2^n )\equiv \left \lfloor 2^{2n}\alpha +2^{2n+3}\alpha \right \rfloor\equiv \left \lfloor \overline{1/k_11k_21k_31...}_{(2)}+\overline{k_2/1k_31...}_{(2)} \right \rfloor\equiv \left \lfloor \overline{(k_2+1)/(k_1+1)(k_3+1)(k_2+1)(k_4+1)...} \right \rfloor\equiv 1\:(mod\:2)$

پس دوحالت داریم:

حالت اول:

$\left \lfloor \overline{(k_2+1)/(k_1+1)(k_3+1)(k_2+1)(k_4+1)...} \right \rfloor=1 \Rightarrow k_1=k_2=k_3=k_4=...=0$

چون اگر یکی از

$k_i$

ها برابر

$1$

باشد، آنگاه رقم یکان در مبنای

$2$

حداقل

$2$

میشود که تناقض است!
در این حالت عدد ما، عددی گویا خواهد بود(کسر متناوب مرکب) که متناقض با فرض ما در مورد گنگ بود آلفاست!

حالت دوم:

$\left \lfloor \overline{(k_2+1)/(k_1+1)(k_3+1)(k_2+1)(k_4+1)...} \right \rfloor=3\Rightarrow k_2=1$

پس به طریق مشابه

$\forall i\in \mathbb{N}$

با

$P(3.2^{n+i})$

میتوان ثابت کرد که

$k_{i+2}=1$

! پس باز هم کسر ما یک کسر متناوب مرکب خواهد شد! که متناقض با فرض گنگ بودن آلفا است!

پس ثابت شد که در هر صورت بی نهایت عدد زوج در برد

$P(n)$

وجود دارد.

$\blacksquare$

math · 1391/1/29

پاسخ : سوال نظریه از نوع hard

threehandsnal گفت

میشه یکم بیشتر توضیح بدین ؟

threehandsnal · 1391/1/29

پاسخ : سوال نظریه از نوع hard

mathh گفت

فرض کنید آلفا عددی گویا باشه.پس فرض کن

$\alpha =\frac{p}{q}$

که p,q صحیح اند! حالا

$P(2^nq)=\left \lfloor 2^{2n}.q^2.\frac{p}{q} \right \rfloor=\left \lfloor 2^{2n}pq \right \rfloor=2^{2n}pq$

که عددی زوجه... :3:

hkh74 · 1391/2/16

پاسخ : سوال نظریه از نوع hard

راه دوم:
اول ببخشید که توضیح اضافی یا کم دادم...
ثابت می کنیم حداقل یک

$n\in\mathbb{N}$

وجود دارد که

$\left \lfloor n^2\alpha \rfloor \right$

زوج شود، و در نهایت از آن حکم را نتیجه می گیریم.
برهان خلف: فرض کنید همه ی اعداد

$\left \lfloor \alpha \right \rfloor,\left \lfloor 4\alpha \right \rfloor,\dots,\left \lfloor n^2\alpha \right \rfloor,\dots$

فرد باشند، تابع

$f:\mathbb{N}\to\mathbb{N}\cup \{0\}$

را به این صورت تعریف می کنیم:

$f(n)$

عددی صحیح نامنفی کوچکتر از

$n^2$

است که

$\frac{f(n)}{n^2}\leq \{\alpha\}< \frac{f(n)+1}{n^2}$

. (

$\{x\}$

جزء اعشاری x است )

از تعریف تابع داریم:

$f(n)\leq n^2\{\alpha\}< f(n)+1\Rightarrow \lfloor n^2\{\alpha\} \rfloor=f(n) \\ \Rightarrow \{n^2\{\alpha\}\}=n^2\{\alpha\}-\lfloor n^2\{\alpha\} \rfloor=n^2\{\alpha\}-f(n)\\ \Rightarrow \{n^2\{\alpha\}\}=n^2\{\alpha\}-f(n)\textbf{ (1)}$

به راحتی می توان ثابت کرد

$\{n^2\alpha\}=\{n^2\{\alpha\}\}$

. پس طبق رابطه (1) :

$\{n^2\alpha\}=n^2\{\alpha\}-f(n)\\ \Rightarrow \lfloor n^2\alpha \rfloor=n^2\alpha-\{n^2\alpha\}=n^2\alpha-n^2\{\alpha\}+f(n)=n^2\lfloor\alpha\rfloor+f(n) \\ \Rightarrow 1=\lfloor n^2\alpha \rfloor=n^2\lfloor\alpha\rfloor+f(n)=n^2+f(n)=n+f(n)\textrm{ (mod 2)} \\ \Rightarrow f(n)\neq n\textrm{ (mod 2)}\textbf{ (2)}$

حال فقط با استفاده از (2) به تناقض می رسیم. مجموعه های

$A_n,B_n(n\in\mathbb{N})$

را به این صورت تعریف می کنیم:

$B_n=\{a\in\mathbb{Z}_{\geq0}:a<n^2\; ,a\neq n\textrm{ (mod 2)}\}$

(

$B_n$

در واقع تمام مقادیری است که

$f(n)$

می تواند اختیار کند)

$A_n=\bigcup_{a\in B_n}\left [ \frac{a}{n^2},\frac{a+1}{n^2} \right )$

(

$A_n$

در واقع تمام مقادیری است که

$\{\alpha\}$

می تواند اختیار کند) پس

$\{\alpha\}\in A_n (\forall n\in\mathbb{N})$

پس

$\{\alpha\}\in \bigcap_{n=1}^{\infty }A_n$

و این یعنی

$\bigcap_{n=1}^{\infty }A_n\neq \varnothing$

. فقط یک مرحله ی نسبتا زشت تا تناقض باقیمانده.

با محاسبات زیاد می توان نشان داد:

$\bigcap_{n=2}^{6}A_n=\varnothing$

پس

$\{\alpha\}\in\bigcap_{n=1}^{\infty }A_n\subseteq \bigcap_{n=2}^{6}A_n=\varnothing$

که تناقضه!

-----------------------------------------------------------------------------------------------------------------------------------------------

پس حداقل یک n وجود دارد، حال فرض کنید تعداد n ها متناهی باشد و تمام n هایی که

$\lfloor n^2\alpha \rfloor$

زوج باشد عبارتند از

$n_1<n_2<\cdots<n_k$

. اگر

$\alpha'=m^2\alpha$

که

$n_k<m\in\mathbb{N}$

، حکم برای

$\alpha'$

هم درست است، یعنی n طبیعی وجود دارد که

$\lfloor (mn)^2\alpha\rfloor=\lfloor n^2\alpha'\rfloor=0\textrm{ (mod 2)}$

ولی

$mn\geq m> n_k$

پس یک ضریب بزرگ تر پیدا شد که حکم برای آن درست است، تناقض!

-----------------------------------------------------------------------------------------------------------------------------------------------

نکته ی مهم: طبق این راه حل

$\forall\alpha\in\mathbb{R}$

حداقل یکی از اعداد

$\lfloor\alpha\rfloor,\lfloor4\alpha\rfloor,\lfloor9\alpha\rfloor,\lfloor16\alpha\rfloor,\lfloor25\alpha\rfloor,\lfloor36\alpha\rfloor$

زوج است، که قویتر از حکم مسأله است.

(با تشکر از threehandsnal عزیز!)

سوال نظریه از نوع hard

حالا هرکی

New Member

threehandsnal

New Member

math

New Member

threehandsnal

New Member

hkh74

New Member