ماراتن المپیاد ریاضی- کاری از دوره طلا

goldeneagle · 1390/12/10

آقا اولا سلام....ثانیا من اوایل هفته یک ایده به ذهنم رسید که بیاییم در اینجا یک ماراتن راه بندازیم...با قواعدی که میگم در ادامه....این ایده رو با گودرز و ماهان هم مطرح کردم که البته به شدت استقبال کردن....خوب قضیه اینه که این ماراتن رو من (بخوانید علیرضا!!!)و ماهان و گودرز و بهزاد می چرخونیم....اول هدفمون این بود که هر دفعه یکی از ما یک سوال ایده دار بذاریم و احیانا بعد دو روز اگر خبری باز نیامد (اساسا آن را که خبر شد خبری باز نیامد...) حلش رو بذاریم.... اما در جلسات بررسی طرح (!!!) شایان عزیزنژاد یک پیشنهاد خوبی داد....پیشنهاد این بود که : " اگه ما فقط سوال ایده دار بذاریم این طرح بیشتر به درد آدمهایی میخوره که ایده ها رو بلدن و اینا...بهتره که لم بذارید و از اون لم سوال بگذارید تا...." (حسش نیس کامل بنویسم...خلاصش این که یعنی این جوری کلی برای شهرستانی ها هم بهتره...ایضا کسانی که دسترسی به کلاسهای پیشرفته ندارن...)

از همه این حرفا که بگذریم میرسیم به نحوه برگزاری ماراتن....هر چند وقت یکبار یکی از ما یک لم یا تکنیک را مطرح میکنه و یک سری سوال هم از اون لم قرار میدهیم....(توجه کنید که یکی یکی سوالها رو قرار میدیم.لذا یکی وسط حل یک سوال نیاد بگه این سواله هم با این ایده حل میشه....مهم اینه که سوالها به ترتیب حل بشن و تا سوالی حل نشده نریم سراغ سوال بعد) بعد سر آخر هم احتمالا می پرسیم آیا کسی سوالی با این ایده داره یا نه. (میگم احتمالا چون شاید به این نتیجه برسیم که همین تعداد سوال کافیه) .

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

در آخر این که لم اول امشب یا فردا صبح همینجا فرستاده میشه....
یا علی....

goldeneagle · 1390/12/10

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

اولین تکنیک vieta jumping یا swaping the roots نام دارد....این ایده در حل یک سری از معدالات دیوفانتی بسیار پرکاربرد است(به خصوص در مواقعی که جوابها محدود است یا جوابی نداریم ).ایده کلی در این روش به این صورت است که در مجموعه جوابها یک عضو را میگیریم که از یک نظر Min باشد مثلا مجموع متغیرها یا بر حسب یکی از متغیرهای معادله....سپس یک معادله درجه دو تشکیل داده و با در نظر گرفتن ریشه دوم آن به تناقض میرسیم...

مثال: a,b دو عدد طبیعی هستند که

$ab+1 \mid a^2+b^2$

ثابت کنید

$\frac {a^{2} + b^{2}}{a \cdot b + 1}$

مربع کامل است. (این یکی تکراری است برای خیلی ها اما خوب مثال خوبی است برای شروع اما کلی سوال دیگه هم هست...یکی یکی )

threehandsnal · 1390/12/10

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

AoPS Forum - One of my favourites problems, yeah! • Art of Problem Solving

Question 6 IMO 1988

راه حل arshakus فک کنم جامع ترین راه حل باشه (20#) و دقیقا از لم یاد شده استفاده کرده است.

bgo · 1390/12/10

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

اینم سوال بعد::3:
همه زوج های (a,b) رو طوری پیدا کنید که

$a|b^2+1,b|a^2+1$

math-sina · 1390/12/10

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

goldeneagle گفت

اولین تکنیک vieta jumping یا swaping the roots نام دارد....این ایده در حل یک سری از معدالات دیوفانتی بسیار پرکاربرد است(به خصوص در مواقعی که جوابها محدود است یا جوابی نداریم ).ایده کلی در این روش به این صورت است که در مجموعه جوابها یک عضو را میگیریم که از یک نظر Min باشد مثلا مجموع متغیرها یا بر حسب یکی از متغیرهای معادله....سپس یک معادله درجه دو تشکیل داده و با در نظر گرفتن ریشه دوم آن به تناقض میرسیم...

مثال: a,b دو عدد طبیعی هستند که

$ab+1 \mid a^2+b^2$

ثابت کنید

$\frac {a^{2} + b^{2}}{a \cdot b + 1}$

مربع کامل است. (این یکی تکراری است برای خیلی ها اما خوب مثال خوبی است برای شروع اما کلی سوال دیگه هم هست...یکی یکی )

توی استراتژی - فصل نظریه اعداد- سوال 14 هم با دو راه حل شده که یکیش همین لم فوق هست.

threehandsnal · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

bgo گفت

فرض کنید

$(m,n)$

یک جواب این معادله باشد به گونه ای که

$m+n$

مینیمال باشد.(بدون کاسته شدن از کلیت سوال فرض کنید

$0< m\leq n$

)

$\left.\begin{matrix} m|n^2+1\\ n|m^2+1 \end{matrix}\right\}\Rightarrow mn|m^2+n^2+1\Rightarrow m^2+n^2+1=kmn$

حال فرض کنید

$P(x,y)=x^2-kxy+y^2+1$

واضح است که:

$P(m,n)=P(km-n,m)=0$

و این یعنی اینکه زوج مرتب

$(km-n,m)$

نیز در شرایط مساله صدق میکند.

و چون

$m+n$

مینیمال است بنابراین خواهیم داشت:

$m+n\leq km-n+m\Rightarrow 2n\leq km\Rightarrow 2n^2\leq kmn$

$0<m\leq n\Rightarrow m=n$

و

$0=m^2-kmn+n^2+1\leq m^2-n^2+1$

$m=n\Rightarrow m|m^2+1 \Rightarrow m=1 \Rightarrow k=3$

بنابراین اگر

$xy|x^2+y^2+1$

آنگاه همواره خواهیم داشت :

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

.

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

$(m,n)$

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

$(m,3m-n)$

رسید بنابراین با توجه به درستی

$(1,1)$

میتوان بینهایت مقدار مطابق با شرایط مساله بدست آورد..این هم دنباله اش:

$(1,1)\rightarrow (1,2) \rightarrow (2,5)\rightarrow (5,13)\rightarrow ...$

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

$a_{n+2}=3a_{n+1}-a_{n}\: \: ;\: n> 2,a_1=a_2=1$

خواهد بود.
که جمله عمومی دنباله این میشه:

$\forall n\in \mathbb{N} :a_n=\left ( \frac{5-2\sqrt{5}}{5} \right ).\left ( \frac{3+\sqrt{5}}{2} \right )^n+\left ( \frac{5+2\sqrt{5}}{5} \right ).\left ( \frac{3-\sqrt{5}}{2} \right )^n$

و چون

$P(x,y)=P(y,x)$

کلیه جوابهای طبیعی این معادله-این ها هستند:

$A=\left \{ (x,y)|\forall n\in\mathbb{N}:x=a_n,y=a_{n+1} \right \}\bigcup \left \{ (y,x)|\forall n\in\mathbb{N}:x=a_n,y=a_{n+1} \right \}$

بوضوح مجموعه

$A$

در تمامی شرایط مساله صدق میکند.

امیدوارم جوبی وجود نداشته باشه :205:

goodarz · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

آفرین. من خوندمش و اشکالی نداشت :3:

اینم سوال بعدی: همه چهارتایی های

$(a,b,m,n)$

از اعداد طبیعی رو پیدا کنید که

$a^mb^n=(a+b)^2+1$

.

threehandsnal · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

goodarz گفت

ابتدا مجموعه جواب این معادله را

$M$

فرض میکنیم(واضح است که اگر

$(a,b,m,n)$

یک جواب معادله باشد آنگاه

$(b,a,n,m)$

نیز یک جواب است.) :

$a^2+2ab+b^2+1-a^mb^n=0\Rightarrow ab|a^2+b^2+1$

با توجه به سوال قبل میتوان گفت:

$a^2+b^2+1=3ab\: \: (1)$

طبق فرض مساله داریم:

$a^2+b^2+1=a^mb^n-2ab\: \: (2)$

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

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

$i)\: m=1\Rightarrow n=2,b=5\Rightarrow a=13\: \vee \: a=2\Rightarrow (2,5,1,2),(13,5,1,2)\in M$

$\Rightarrow (5,2,2,1),(5,13,2,1)\in M$

$ii)a=1\Rightarrow b=5,n=2\Rightarrow \forall m\in \mathbb{N}:(1,5,m,2)\in M$

که با جایگذاری در میابیم که قابل قبول نیست!

حال اگر

$a,b,m,n>1$

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

$M=\left \{ (2,5,1,2),(5,2,2,1),(13,5,1,2),(5,13,2,1) \right \}$

Aref · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

threehandsnal گفت

دو تای آخری که جواب نیستند.
PS:
بدون vieta jumping هم میشه

threehandsnal · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

Aref گفت

مرسی-تصحیح شد.

Aref · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

goodarz گفت

واضحه که اگه

$(a,b,m,n)$

جواب باشه

$(b,a,n,m)$

هم جوابه. پس بدون کاستن از کلیت مساله فرض کنید:

$a\ge b$

.
سه حالت را در نظر می گیریم:

$m>2$

:
داریم:

$4a^2+1\ge (a+b)^2+1=a^mb^n\ge a^3$

حالا چون رشد سمت چپ نامساوی از رشد سمت راست بیشتره، مقادیری که

$a$

اخذ می کنه محدود هستند. در واقع اگر

$a>3$

اونوقت سمت راست از سمت چپ بزرگتره. اگر هم

$a\le 3$

با چک کردن می بینیم که هیچ جوابی نداریم.

$m=2$

:
اگر

$b^n\ge 5\Rightarrow 5a^2\le a^2b^n=(a+b)^2+1\le 4a^2+1$

که تناقض می باشد.
اگر

$b^n\le 4$

هم با چک کردن می بینیم که تنها جواب

$(5,2,2,1)$

هستش.

$m=1$

:
واضح است که

$a\neq b$

. پس

$a>b$

.
به معادله ی

$ab^n=a^2+b^2+2ab+1$

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

$a$

است. فرض کنید

$c$

ریشه ی دیگر این معادله باشد. به وضوح داریم

$c\le b$

؛ پس چون

$(c,b,1,n)$

هم جوابی از معادله ی اولیه است پس دو حالت داریم:

حالت اول:

$(c,b,1,n)=(2,5,1,2)\Rightarrow (a,b,m,n)=(13,5,1,2)$

حالت دوم:

$n=1$

به وضوح در این حالت هم جوابی نداریم.

goodarz · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

خیلی ممنون از راه حل هایی که دادین. یه نکته آموزنده هم که آقا عارف بهش اشاره کردن اینه که سعی کنید همیشه وقتی جوابی رو به دست میارید, اونو چک کنید, مثلا اگه دارید یه سوال تابعی حل می کنید و رسیدید به یه ضابطه برای تابع, حتما چک کنید و ببینید که تو معادله تابعی کار می کنه یا نه, یا مثلا وقتی دارید یه سوال هندسه رو حل می کنید که مثلا اندازه یه زاویه ایو ازتون خواسته, وقتی اون اندازه رو بدست آوردین حتما چک کنین که کار بکنه ....... معمولا یه بخشی از نمره سوال به همین چک کردن اختصاص داره, پس هیچ وقت این کارو فراموش نکنین :3:

threehandsnal · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

goodarz گفت

در مورد من جالب اینجاست که چندین بار تمامی جواب ها رو چک کردم توی این سوال و هر بار

$(5+1)^2=24$

بدست آوردم و واسه همین فک کردم این هم جواب میده x_X دیگه اوج جوب بود D:

goldeneagle · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

goodarz گفت

یک مثال عجیب :
درالمپیاد جهانی سال 2002 که مرز طلا 29 بود یکی از اعضا تیم 28 شد و نقره داغ شد....ایشون از سوال 5 که تابعی بود از 7 نمره 6 نمره گرفت که آن یک نمره رو بر سر چک نکردن جواب از دست داد....
البته در المپیاد جهانی امسال هم سوال 1 برای چک کردن گویا نمره وجود داشت البته خوبی قضیه این بود که در المپیاد جهانی چک کردن در چکنویس هم قبول است!!!

mahanmath · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

همه ی‌

$(m,n)$

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

$mn-1 \mid (n^2 -n+1)^2$

Aref · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

mahanmath گفت

من اینو قبلا حل کردم. حلش یکم طولانی بود از vieta jumping و معادله ی پل استفاده کردم. اگه اشتباه نکنم TST آمریکا بوده.

Kavoshgar · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

Aref گفت

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

ash1374 · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

mn-1|(n[SUP]2[/SUP]-n+1)[SUP]2[/SUP] -->mn-1|(m+n-1)[SUP]2[/SUP]

حالا این نسبت بخشپذیری رو مثلا t میگیریم. اگر m=n براحتی جواب m=n=2 در میاد. پس فرض می کنیم m>n و در بین تمام زوج های mوn اکه اون نسبت tبشه اونی رو که mمینیمم باشه می گیریم. حالی یه معادله ی درجه 2 بر حسب mداریم.

m[SUP]2[/SUP]+n[SUP]2[/SUP]+1-2mn-2m-2n-tmn+t=0

پس این معادله یه جواب دیگه هم داره که اگه از روی ضرایب و اتحاد ویت حسابش کنیم همون n-1)[SUP]2 [/SUP]+t /m میشه که طبیعیه و با نامساوی میشه نشون داد برای n>1 از m کوچیکتره . که با فرض مینمم بودن m تناقضه. n=1 هم جواب m=2 رو میده.
ولی از معادله ی پل استفاده نشد. اگه جایی اشتباه کردم لطفا بهم بگید.
[HR][/HR]

goldeneagle · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

Aref گفت

اگه قرار بود این جوری حل کنیم که دیگه ماراتن نمی خواست.... یک سری لینک از مرحوم(!!!) Mathlinks می دادیم ملت برن خودشون سوال و جواب بخونن!!!! قراره بقیه هم چیزی یاد بگیرن.... البته ببخشید اگه یک ذره لحنم تند بود اما نظرم بود :3:
در ضمن من فکر کنم خوبه منابع سوالها گفته بشه....

اون سوالی که گودرز گذاشت انتخاب تیم 2006 رومانی بود....این یکی هم انتخاب تیم 2009 آمریکا....

hkh74 · 1390/12/11

پاسخ : ماراتن المپیاد ریاضی- کاری از دوره طلا

mahanmath گفت

اول از همه یک تشکر بابت این ماراتن...

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

چون جواب

$(m,n)$

جواب

$(n,m)$

را نتیجه می دهد، می توانیم فرض کنیم

$n\geq m$

. (اگر دو طرف را در

$m^4$

ضرب کنیم و از

$mn\equiv 1 \mathrm{\; (mod\; mn-1)}$

استفاده کنیم، از یک جواب به جواب دیگر می رسیم)

چون حالت m=n تنها به جواب های

$(m,n)=(1,1)\: ,(2,2)$

می رسد، فرض می کنیم

$n>m$

.

اگر m=1 جواب های

$(m,n)=(1,1)\: ,(1,2)$

به دست می آید. پس فرض می کنیم m>1. در بین جواب های

$(m,n)$

برای این حکم (که n>m>1 ) جوابی را انتخاب می کنیم که m کمترین مقدار ممکن باشد. همچنین در بین این جواب(ها) جوابی را انتخاب می کنیم که n کمترین مقدار باشد.

$(n^2-n+1)^2\equiv 0\Rightarrow m^2(n^2-n+1)^2\equiv 0\Rightarrow (n-1+m)^2\equiv 0 \; (mod\: mn-1) \\ \Rightarrow mn-1|m^2+n^2+2mn-2m-2n+1\Rightarrow mn-1|m^2+n^2-2m-2n+3 \\ \Rightarrow m^2+n^2-2m-2n+3=k(mn-1)\Rightarrow n^2-(2+km)n+\left ((m-1)^2+k+2 \right )=0$

چندجمله ای درجه دوم

$P(x)=x^2-(2+km)x+\left ((m-1)^2+k+2 \right )=0$

یک ریشه ی طبیعی(n) دارد. فرض کنیم ریشه ی دیگرش

$n'$

باشد.

$n+n'=2+km\; ,nn'=(m-1)^2+k+2$

از اولی به دست می آید

$n'$

صحیح است و از دومی به دست می آید

$n'>0$

پس

$n'$

طبیعی است. اکنون برای اینکه ثابت کنیم مسئله جواب دیگری ندارد کافی است ثابت کنیم

$n'<n$

(اثبات بازگشتی):

$n'<n\Leftrightarrow n+n'<2n\Leftrightarrow 2+km<2n\Leftrightarrow k<\frac{2(n-1)}{m} \\ \Leftrightarrow \frac{m^2+n^2-2m-2n+3}{mn-1}<\frac{2(n-1)}{m}$

که حکم آخر هم با طرفین وسطین به شکل زیر تبدیل و اثبات می شود:

$mn^2-2n+2>m^3-2m^2+3m \\ mn^2-2n+2=n(mn-2)+2\geq (m+1)(m(m+1)-2)+2=m^3+2m^2-m>m^3-2m^2+3m$

پس تنها جواب ها

$(m,n)=(1,1)\: ,(1,2)\: ,(2,1)\: ,(2,2)$

است.

ماراتن المپیاد ریاضی- کاری از دوره طلا

New Member

New Member

New Member

New Member

New Member

New Member

Well-Known 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

New Member