ماراتن نظریه ی اعداد (سطح ممتاز)

TheOverlord · 1393/7/5

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

دنباله

$a_n$

رو از عقب هم ادامه بدید و برای n های منفی هم تعریف کنید.
بدیهتا

$a_3=a_2a_1+a_0 \Rightarrow a_0=0$

، و دقت کنید که

$a_n=a_{n+3}-a_{n+1}a_{n+2}$

یعنی با داشتن سه عضو متوالی دنباله قبلی هم بطور یکتا مشخص میگردد.
حال گرافی m^3 راسی بسازید و هر راسش را با سه تایی مرتبی که هر کدام از اندیس هایش عددی طبیعی بین 1 تا m است برجسب گذاری کنید. از راس با برچسب

$(a_0,a_1,a_2)$

شروع کنید و هر مرحله یالی جهت دار از

$(a_n,a_{n+1},a_{n+2})$

به

$(a_{n+1},a_{n+2},a_{n+3})$

(ai ها را به پیمانه m در نظر بگیرید)رسم کنید. بدیهتا چون تعداد رئوس گراف متناهی است پس جایی به راس تکراری برخورد میکنیم. اولین جا را در نظر بگیرید که چنین اتفاقی بیفتد. دقت کنید که از آنجا که میتوان از سه عضو متوالی دنباله قبلی را هم پیدا کرد پس درجه ورودی هر راس حداکثر یک است. اما چون هر راس تکراری از راس قبلی اش در دنباله هم یال میگرفته پس اگر اولین راس تکراری همان (0و1و1) نباشد پس یال دیگری هم به آن وارد میشده، که تناقض است. بنابرین دوباره به راس (0و1و1) میرسیم و با ادامه باز هم به این راس میرسیم پس نامتناهی بار به این راس میرسیم، اما رسیدن به این راس همانا و پیدا کردن عددی جدید بخش پذیر بر m همانا، چرا که وجود 0 در این راس نشانگر بخش پذیر بودن عضو اول سه تایی مرتب بر m است که چون عضوی از دنباله است که در رئوس دیگر ظاهر نشده پس عدد جدیدی بخش پذیر بر m داریم پس بینهایت مضرب m در این دنباله موجود است.

سوال بعد: جدول شطرنجی n*n داریم که اعداد 1 تا

$n^2$

به ترتیبی درون آن قرار داده شده اند. فرض کنید s1 جمع اعداد درون خانه های سیاه و s2 جمع اعداد درون خانه های سفید باشد. همه n هایی را بیابید که به ازای آنها ترتیبی از اعداد 1 تا

$n^2$

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

$\frac{s1}{s2}=\frac{64}{39}$

aras2213 · 1393/7/11

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

$\frac{s_{1}+s_{2}}{s_{2}}=\frac{103}{39}\rightarrow s_{2}=\frac{n^2(n^2+1)\times 39}{103\times 2}$

حالا چون 103 عددی اول به شکل 4k+3 هست،نمیتونه n^2+1 رو عاد کنه پس

$103\mid n$

حالا نشون میدیم این شرط کافی هم هست.فرض کنید n زوچ باشه.میخوایم n^2/2 عدد رو تو جدول قرار بدیم که جمعشون s2 بشه.حالا دقت کنید که:

$1+...+\frac{n^2}{2}\leqslant s_{2}\leqslant (\frac{n^2}{2}+1)+...+n^2$

پس i ای وجود داره که:

$i+...+(\frac{n^2}{2}+i-1)\leqslant s_{2}\leqslant (i+1)+...+(n^2/2+i)$

حالا چون اختلاف سمت راست و چپ برابر n/2 هه،اگر s2 با سمت چپ k تا اختلاف داشته باشه که k کوچکتر یا مساوی با n/2 هه،اگه به k عضو بزرگتر از سمت چپ به هر کدام یکی اضافه کنیم به s2 میرسیم.پس n^2/2 عدد پیدا شد که جمعشان s2 باشد و این اعداد را در خانه های سفید قرار میدهیم.

aras2213 · 1393/7/13

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

سوال بعد:
p عددی اول به شکل 4k+3 است.x,y,,z,t هم اعدادی طبیعی هستند که

$x^{2p}+y^{2p}+z^{2p}=t^{2p}$

.نشان دهید

$p\mid xyzt$

.

Dadgarnia · 1393/7/21

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

aras2213 گفت

فرض مي كنيم

$p\not | xyzt$

پس

$\gcd(p,x)=\gcd(p,y)=\gcd(p,z)=\gcd(p,t)=1$

حالا مي تونيم از قضيه ي كوچك فرما استفاده كنيم و يه جوري به تناقض برسيم:65:
يه راهنمايي مي كنيد؟

aras2213 · 1393/7/21

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

Dadgarnia گفت

:4:

اول با توجه به اون معادله میشه فرض کرد که ب.م.م x,y,z,t برابر با 1 هستش.حالا زوجیتشون رو بررسی کنید و با توجه به زوجیت، یکی از x,y,z رو اون طرف معادله ببرید و سعی کنید یه عامل اول به شکل 4k+3 سمت راست معادله ایجاد کنید.

Dadgarnia · 1393/7/26

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

aras2213 گفت

ابتدا مي تونيم فرض كنيم

$\gcd(x,y,z,t)=1$

و اگه دو طرف رو به پيمانه ي ٤ در نظر بگيريم مي تونيم بفهميم كه از بين x,y,z دو تا زوج و يكي فرد هستند. فرض مي كنيم z فرد باشه پس داريم:

$x^{2p}+y^{2p}=t^{2p}-z^{2p}=(t^2-z^2)(\sum_{i=0}^{p-1}t^{p-i-1}z^i)(\sum_{i=0}^{p-1}(-1)^it^{p-i-1}z^i)$

عبارت

$\sum_{i=0}^{p-1}t^{p-i-1}z^i$

به شكل

$4k+3$

است پس عامل اولي مانند q داره كه به همون شكله و توان q در اين عبارت عددي فرده پس داريم:

$q|x^{2p}+y^{2p}\Rightarrow q|x,q|y$

حالا اگه داشته باشيم

$v_q(x+y)=\alpha$

بدست مياد

$v_q(x^{2p}+y^{2p})=2p\alpha\equiv 0(mod \ 2)$

پس از طرف ديگر داريم:

$v_q(\sum_{i=0}^{p-1}t^{p-i-1}z^i)\equiv 1(mod \ 2),v_q(\sum_{i=0}^{p-1}(-1)^it^{p-i-1}z^i)\equiv 0(mod \ 2)\Rightarrow v_q(t^2-z^2)\equiv 1(mod \ 2)\Rightarrow q|t^2-z^2$

پس q بايد حداقل يكي از دو عبارت

$x+y,x-y$

رو بشماره اما اگه q،

$x+y$

رو بشماره داريم:

$q|t^p+z^p,q|t^p-z^p\Rightarrow q|t,q|z$

كه اين با فرض اوليه ي ما در تناقضه. حالا داريم:

$v_q(t-z)\equiv 1(mod \ 2)\Rightarrow 0 \equiv v_q(t^{2p}-z^{2p})=v_q(t-z)+v_q(2p)\equiv 1+v_q(2p)(mod \ 2)\Rightarrow q|2p\Rightarrow q=p$

از قبل داشتيم

$q|x,q|y$

پس چيزي كه مي خواستيم ثابت شد.

TheOverlord · 1393/7/26

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

Dadgarnia گفت

چرا اين درست است؟ لم دو خط چيز ديگري ميگويد.

Dadgarnia · 1393/7/26

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

TheOverlord گفت

نه ما اينجا نمي تونيم از لم دو خط استفاده كنيم چون

$q|x,q|y$

TheOverlord · 1393/7/26

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

Dadgarnia گفت

ممنون، صورت لم رو فراموش كرده بودم.
سوال بعد: همه اعداد طبيعي را بيابيد كه بطور يكتا به صورت

$\frac{x^2+y}{xy+1}$

باشند كه در آن x,y طبيعي هستند.

Dadgarnia · 1393/7/27

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

TheOverlord گفت

فرض کنید

$\frac{x^2+y}{xy+1}=n$

باشه. ابتدا حالتی رو در نظر می گیریم که

$n=1$

باشه. در این حالت به راحتی می تونیم بدست بیاریم که 1 به شکل های زیر قابل نوشتنه:

$\frac{1^2+x}{1x+1},\frac{x^2+(x+1)}{x(x+1)+1}$

پس 1 رو به بی نهایت طریق می تونیم به این شکل بنویسیم. در حالتی که

$y=1$

باشد به راحتی می تونیم بدست بیاریم

$x=n=1$

. حالا فرض می کنیم

$n,y\geq 2$

داریم:

$x^2+(-ny)x+(y-n)=0$

اگه دلتای این معادله رو تشکیل بدیم باید به ازای

$m$

ای طبیعی داشته باشیم:

$n^2y^2+4n-4y=m^2$

حالا سه حالت رو در نظر می گیریم:
1-

$n>y$

$(ny)^2<m^2<(ny+1)^2$

که تناقضه.
2-

$n<y$

$(ny-1)^2<m^2<(ny)^2$

که اینم تناقضه.
3-

$n=y$

که در این حالت داریم:

$x=n^2$

پس هر عدد طبیعی بزرگتر از یک به صورت یکتا قابل نمایش به این شکل است.
سوال بعد:
ثابت کنید معادله ی

$3y^2=x^4+x$

هیچ جوابی در مجموعه ی اعداد صحیح مثبت ندارد.

m-saghaei · 1393/7/27

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

Dadgarnia گفت

داریم:

$3y^2=x(x+1)(x^2-x+1)$

و روابط روبه رو رو هم داریم:

$(x,x+1)=1,(x,x^2-x+1)=1,(x+1,x^2-x+1)=1,3$

اگه ب.م.م شون برابر 3 باشه اونوقت

$x=3k-1$

بعد اگه همین رو تو اون عبارت تجزیه شده صورت سوال بزاریم نتیجه میشه

$y=3s$

که بعد دوباره تو صورت سوال اینو بزاریم میده

$k=3t$

و دوباره (!) اگه جایگذاری کنیم میشه:

$s^2=(9t-1)t(27t^2-9t+1)$

که چون ب.م.م دوبه دوشون یکه باید هر کدوم یه مربع کامل باشن که این درباره

$9t-1=a^2$

صدق نمیکنه.
اگه ب.م.م شون برابر یک باشه اونوقت دو حالت وجود داره.یکی اینکه

$(x+1,x^2-x+1)=(x,3)=(x+1,3)=1$

که نتیجه میشه

$x=a^2,x+1=b^2$

که اینم فقط تو

$x=0,y=0$

صدق میکنه.اون یکی حالت اینه که ب.م.م اون دوتا یک باشه ولی

$3|x(x+1)$

یعنی

$x=3k,3k+2$

که اینم نتیجه میشه باید

$x^2-x+1=a^2$

که اینم اگه ضربدر 4 کنیم تجزیه کنیم میشه دو تا جواب

$x=0,1$

رو داره که

$x=1$

برقرار نیست.

پس در کل فقط

$x=0,y=0$

جوابه یعنی جوابی در مجموعه اعداد صحیح مثبت ندارد.

Dadgarnia · 1393/7/29

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

سوال بعد:
تمام

$x,y,z$

های صحیح مثبت را بیابید به طوریکه داشته باشیم

$x^5+4^y=2013^z$

.

AHZolfaghari · 1393/8/1

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

Dadgarnia گفت

اول اثبات می کنیم که y بر 5 بخش پذیره . بعد طرف چپ رو تجزیه می کنیم . و از تجزیه 2013 استفاده می کنیم . ب م م اون دو تا عبارت طرف چپ رو هم باید در نظر داشت

aras2213 · 1393/8/6

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

سوال بعد:همه چند جمله ای های با ضرایب صحیح را بیابید که برای هر

$n> 2213$

( :4:...:4: )داشته باشیم

$f(n)\mid n^{n-1}-1$

.

TheOverlord · 1393/8/12

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

لم:

$(a,b)=1 \Rightarrow (a^n-b^n,a^n-b^m)=a^{(n,m)}-b^{(n,m)}$

لم:

$f(n)|f(n+f(n))$

فرض کنید ضریب پیشروی

$f$

مثبت است (در غیر این صورت آن را در یک منفی ضرب میکنیم) پس از جایی به بعد مثبت است. فرض کنید

$n$

از آنجا به بعد باشد و از 2213 نیز بزرگتر باشد.واضح است که

$(n,f(n))=1$

پس داریم:

$f(n)|f(n+f(n))|(n+f(n))^{n+f(n)-1}-1\overset{f(n)}\equiv n^{n+f(n)-1}-1 ,f(n)|n^{n-1}-1\Rightarrow f(n)|n^{n-1}(n^{f(n)}-1)\Rightarrow f(n)|n^{f(n)}-1$

فرض کنید که

$f(n)=(n-1)^mp(n):p(1)\not=0$

. بدیهی است که

$p(n)|f(n)|n^{n-1}-1$

پس

$p(n)$

نیز در شرایط مساله صدق میکند یعنی با اثباتی مشابه میتوانیم نتیجه بگیریم

$p(n)|n^{p(n)}-1$

همچنین فرض کنید بنابر الگوریتم تقسیم

$p(n)=(n-1)q(n)+r : r\not=0$

پس

$p(n)|n^{(n-1)}^{q(n)}-1 , p(n)|n^{(n-1)q(n)+r}-1 \Rightarrow p(n)|n^{|r|}-1$

اما کافیست فرض کنید

$(n-1,|r|)=1 \Rightarrow p(n)|(n^{n-1)-1,n^{|r|}-1})=n^{(n-1,|r|)}-1=n-1$

واضح است که بینهایت

$n$

با این خاصیت موجودند پس عادکردن چند جمله ای است. اما طبق

$p(1)\not=0$

بدیهی است که در این صورت

$p(n)$

ثابت است. پس

$f(n)=c(n-1)^m$

اما اگر

$n$

را طوری بگیرید که

$c|n \Rightarrow c|n^{n-1} , c|n^{n-1}-1 \Rightarrow c=\pm 1$

همچنین اگر

$n$

عددی اول به اضافه یک باشد طبق لم دوخط بدیهی است که

$m\leq 2$

و طبق لم دوخط ثابت میشود که برای هر سه حالت درست است. پس جواب برابر است با :

$f(n)=\pm1,\pm(n-1),\pm(n-1)^2$

TheOverlord · 1393/8/12

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

همه

$n$

های طبیعی را بیابید که

$221|n^{n^{n^n}}-n^{n^n}$

Dadgarnia · 1393/8/12

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

TheOverlord گفت

AoPS Forum - A 10 • Art of Problem Solving البته این برای 1989 هه و 221 هم که مقسوم علیه همین عدده.

---- دو نوشته به هم متصل شده است ----

برای n=1 که برقراره و برای n=2 هم داریم:

$2^{16}\equiv 1\pmod{17}\Rightarrow 17\nmid 2^{16}-16$

---- دو نوشته به هم متصل شده است ----

سوال بعد:
تمام توابع

$f:\mathbb{N} \mapsto \mathbb{N}$

را بیابید که برای هر a,b طبیعی

$af(a)+bf(b)+2ab$

مربع کامل باشد.

m-saghaei · 1393/8/12

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

Dadgarnia گفت

این راه درسته؟مطمئن نیستم!

اول میایم یه عدد اولی مثل p میزاریم:

$2pf(p)+2p^2=m^2\rightarrow 2p(f(p)+p)=m^2\rightarrow p|f(p)$

حالا میزاریم

$a=p,b=1$

در نتیجه:

$pf(p)+2p+f(1)=m^2$

یه بارم میزاریم

$a=p,b=2$

در نتیجه:

$pf(p)+4p+2f(2)=n^2$

پس:

$n^2-m^2=2p+2f(2)-f(1)$

حالا از این دوتا و این که m و n از

$\sqrt{2}p$

بزرگترن استفاده میکنیم.آخرش نتیجه میشه

$f(p)=p$

حالا از یه عددی مثل t و عدد اول دیگه ای مثل q استفاده میکنیم:

$tf(t)+q^2+2tq=m^2$

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

$(t+q)^2\leq tf(t)+q^2+2tq< (t+q+1)^2$

پس باید داشته باشیم:

$(t+q)^2=tf(t)+q^2+2tq\rightarrow f(t)=t$

درنتیجه برای هر عددی اثبات شد داریم

$f(a)=a$

درسته؟

TheOverlord · 1393/8/12

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

چرا

$t^2 \leq tf(t)$

در خط دو تا مانده به آخر؟

m-saghaei · 1393/8/13

پاسخ : ماراتن نظریه ی اعداد (سطح ممتاز)

TheOverlord گفت

ممنون که گفتید.الان خودم اینجاش گیج شدم!!!فکر کردم t اوله.چون اگه اول باشه اونو داریم.

همین تیکه آخرشو یه جور دیگه میگم.امیدوارم این دیگه درست باشه.

این رو داریم که

$tf(t)+q^2+2qt$

باید مربع کامل باشه.پس

$t(f(t)-t)+(t+q)^2$

مربع کامله.

حالا اگه داشته باشیم اونوقت چون مربع کامل بعد

$(t+q)^2$

,

$(t+q+1)^2$

هه پس باید داشته باشیم:

که اینم چون اشتباهه.چون اگه q مثلا 3 باشه: که اگه طرف چپ رو بزرگش هم کنیم منفی میشه.

حالا اگه داشته باشیم

$f(t)<t$

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

پس باید داشته باشیم

$f(t)=t$

این یکی چی؟درسته؟

ماراتن نظریه ی اعداد (سطح ممتاز)

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member

Well-Known Member

New Member

New Member

New Member

New Member

New Member

New Member

New Member