تعداد جواب های معادله ${1\over x}+{1\over y}={1\over n}$ در دستگاه اعداد صحیح
روشن کردن چراغ های خانه به طوری که هر اتاق چراغ خاموش و روشن داشته باشد(بالا خره حل شد!)
n نفر با کلاه های قرمز و آبی و حدس زدن بیشترین تعداد درست
سوال 3 روز اول مرحله دوم چهارمین المپیاد کامپیوتر ایران
برابر بودن یا نبودن تعداد اعداد زوج و فرد
یافتن تعداد مستطیل های یک شبکه نقطه ای
فرض کنید S اجتماع تعدادی مجموعه های متناهی و k عددی ثابت باشد...
n لامپ خاموش و n کلید داریم .(در وضعیت اولیه لامپها همه خاموشند) اگر کلید شماره k را بزنیم لامپهایی که شماره آنها مضرب k هست تغییر وضعیت میدهند.ثابت کنید که میتوانیم همه وضیتهای لامپها را با زدن مجموعه ای از کلیدها بسازیم یا به عبارتی یه مجموعه منحصر به فردی از کلیدها برای هر وضعیت لامپها وجود دارد به طوریکه اگر آنها را بزنیم آن وضعیت حاصل میشود
از ۱ شروع می کنیم و هر عددی که تمام مقسوم علیه های محضش انتخاب شدن کلیدش رو بررسی می کنیم همچی به طور یکتا تعیین میشه.
2019-06-16 11:26:55 -0600 طاها اکبرییه سوال مرحله 2 شبیه این بود. یا این اسکی از اونه یا اون اسکی از اینه :)
2019-06-18 13:58:16 -0600 غزوواینم جواب خودم :D
خوب یه گراف 2 بخشی میسازیم .یه طرف$ 2^n $که حالت کلیدزدن مختلف هست و طرف دیگه b هست که$ 2^n $ و برابر تعداد وضعیت لامپهاست
حالا میگیم هر حالت کلید زدن یه وضعیت لامپ رو نتیجه میده پس تعداد یالهای گراف 2 بخشیمون$ 2^n $هست.
حالا فرض خلف میکنیم که یه وضعیت لامپ هست که نمیشه اونو ساخت
در واقع درجه اون راس در مولفه b صفر هست . پس در مولفه b حداقل 1 راس با درجه حداقل 2 وجود داره مثلا x
یعنی یک وضعیت هست که توسط 2 حالت کلیدزدن بوجود میاد یعنی 2 مجموعه متفاوت Y , Z هست که اگر کلیدای اون 2 مجموعه رو بزنیم وضعیت x رو به ما میده
حالا این 2 مجموعه رو در نظر میگیریم و کلید های مشترک 2 مجموعه رو اگر بزنیم به 2 تا مجموعه جدید $ A , B $میرسیم که کلیدهاشون هیچ اشتراکی باهم ندارن . حالا بازم 2 تا مجموعه کوچکتر متفاوت داریم که باید 1 وضعیتو نتیجه بدن . حالا کوچکترین شماره کلید مجموعه A که برابر V و کوچکترین شماره کلید مجموعه B برابر U رو در نظر میگیریم
میدونیم اگر$ U > V $باشه خود لامپ V در مجموعه A روشنه اما در مجموعه B روشن نیست چون در B همه شماره کلیدها از V بیشترند هیچ عددی در B نیست که مضرب آن ، عدد V را بدهد
پس V درانتها در B روشن نمیشود که تناقض است ؛ پس A , B نتیجه یکسانی نمیدهند :) و درحالت$ V > U $هم برعکس اینه :))))
یک وضعیت از تمامی لامپ ها را با یک دنباله از 0 و 1 مانند $P$ نشان دهیم که $p_i=1$ اگر تنها اگر لامپ $i$ام روشن باشد ($p_i$ عضو $i$ام دنباله ی $P$ است.)
فرض کنید در نهایت میخواهیم وضعیت لامپ ها متناظر دنباله ی $A$ باشد.الگوریتمی ارائه میدهیم که در آن با انتخاب چند کلید از هر وضعیت اولیه لامپ ها به $A$ برسیم وحکم ثابت شود. در این الگوریتم مجموعه ی کلید هایی که باید زده شود را در مجموعه ی $C$ میریزیم.
فرض کنید در مرحله ای از الگوریتم وضعیت لامپ ها بصورت دنباله ای مانند $B$ است. لامپ $i$ام را اوکی میگوییم اگر و تنها اگر $b_i=a_i$.
الگوریتم به این صورت است:
به ازای $i$ از 1 تا $n$ کارهای زیر را انجام بده:
بعد از این الگوریتم مجموع ی $C$ ما را از دنباله ی اولیه به دنباله ی $A$ میرساند. زیرا به ازای هر $i$ پس از مرحله ی $i$ام لامپ شماره ی $i$ اوکی میشود و همچنین در مراحل بعد اگر کلیدی مانند $j$ انتخاب شود $j>i$. در نتیجه انتخاب کردن یا نکردن آن کلید تغییری در وضعیت لامپ $i$ نمی گذارد.
پس حکم ثابت میشود.
عاورین :))) البته من اصل سوالو عوض کرده بودم (الان هم تو ویرایش اصلشو نوشتم)؛ و و خودم هم از تناظر حل کرده بودم ولی خوب انتظار نداشتم اینجوری حل شه :)
2019-06-17 11:01:47 -0600 صفر و یک