المپیاد آرشیو سوالات از گذشته تا کنون

[mathematician]

پاسخ : آرشیو سوالات از گذشته تا کنون

یه سوال جالب دیگه:

فرض کنید به اعدادی که فقط از ارقام 1 و 0 تشکیل شده باشند، می گیم اعداد ایده آل!

ثابت کنید به ازای هر عدد طبیعی n، عدد ایده آلی وجود داره که بر n بخش پذیره!

(مثلاً اگه n = 14 عدد ایده آل 1111110 بر 14 بخش پذیره!!)

این n+1 عدد رو در نظر می گیریم:
1 , 11 , 111 ,1111 , ... , 1111111..111 (n+1 bar)
طبق اصل لانه ی کبوتری حداقل دوتا از این اعداد در تقسیم بر nباقیمانده های یکسان دارن پس تفاضل این دو عدد برn بخشپذیره و تنها از 1 و 0 تشکیل شده.

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

این n+1 عدد رو در نظر می گیریم:
1 , 11 , 111 ,1111 , ... , 1111111..111 (n+1 bar)
طبق اصل لانه ی کبوتری حداقل دوتا از این اعداد در تقسیم بر nباقیمانده های یکسان دارن پس تفاضل این دو عدد برn بخشپذیره و تنها از 1 و 0 تشکیل شده.

درسته!

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

رنگ آمیزی صفحه :

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

الف) آیا می تونیم با استفاده ار 2 رنگ، رنگ آمیزی مناسب داشته باشیم؟!

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

ب) آیا می شه با استفاده از 3 رنگ، رنگ آمیزی مناسب داشت؟!

راهنمایی: باز هم نه!

ج) با 7 رنگ چه طور؟!

راهنمایی: آره! با 7 رنگ می شه یه رنگ آمیزی مناسب داشت! (سعی کنید صفحه رو با 7 رنگ به گونه ای رنگ آمیزی کنید که هیچ دو نقطه ای به فاصله ی یک، هم رنگ نباشند! خیلی سخت نیست!!)


جالبه بدونید که درباره ی 4 و 5 و 6 رنگ هنوز چیزی ثابت نشده!! (در واقع نمی دونیم حداقل تعداد رنگ لازم برای داشتن یه رنگ آمیزی مناسب چندتاست؟! فقط می دونیم جواب یا 4 هست یا 5 یا 6 و یا 7)

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

همين جوري: من شايد از اين به بعد كم تر اين جا فعاليت كنم!! (البته سعي مي كنم فعاليتم كم نشه!!) اميدوارم المپياد كامپيوترياي اين جا، بيش تر فعاليت كنن!! باز هم تاكيد مي كنم كه شرط لازم و كافي براي قبولي توي مرحله اول و دوم المپياد كامپيوتر سوال حل كردنه!! تا مي تونيد سوال حل كنيد!! سوال هاي متنوع كه با ايده هاي مختلفي حل بشن!!

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

یه سوال نه چندان سخت:

یه جدول 5 * 5 داریم که توی هر کدوم از خونه هاش یه مورچه قرار داره!! با صدای سوت ما، هر کدوم از مورچه ها به یکی از خونه های مجاور خودشون می رن!! (دو خونه وقتی مجاور هستند که ضلع مشترک داشته باشند!!) ثابت کنید بعد از یه بار سوت زدن، حد اقل یکی از خونه ها خالی خواهد ماند!!

 

[armita]

پاسخ : آرشیو سوالات از گذشته تا کنون

فرض مي كنيم خونه هاي جدول مثل شطرنج يك در ميون سياه سفيدن و تعداد سفيد ها يكي بيشتره.پس اولش ١٢ مورچه رو خونه هاي سياهن و ١٣ تا سفيد. وقتي سوت بزنيم سفيد ها بايد برن تو خونه سياه و بر عكس!(چون همسايه هاي هر خونه رنگشون با اون خونه فرق داره)در نتيجه ١٣ تا از سفيد ها مي رن تو ١٢ تا سياه و بر عكس! پس يه خونه سفيد خالي مي ميمونه!

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

یه جدول 5 * 5 داریم که توی هر کدوم از خونه هاش یه مورچه قرار داره!! با صدای سوت ما، هر کدوم از مورچه ها به یکی از خونه های مجاور خودشون می رن!! (دو خونه وقتی مجاور هستند که ضلع مشترک داشته باشند!!) ثابت کنید بعد از یه بار سوت زدن، حد اقل یکی از خونه ها خالی خواهد ماند!!

فرض مي كنيم خونه هاي جدول مثل شطرنج يك در ميون سياه سفيدن و تعداد سفيد ها يكي بيشتره.پس اولش ١٢ مورچه رو خونه هاي سياهن و ١٣ تا سفيد. وقتي سوت بزنيم سفيد ها بايد برن تو خونه سياه و بر عكس!(چون همسايه هاي هر خونه رنگشون با اون خونه فرق داره)در نتيجه ١٣ تا از سفيد ها مي رن تو ١٢ تا سياه و بر عكس! پس يه خونه سفيد خالي مي ميمونه!

درسته!

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

یه سوال دیگه:

فرض کنید 10 عدد طبیعی متمایز داریم و همگی این اعداد هم از 107 کوچک ترند! ثابت کنید می شه 2 زیر مجموعه ی مجزا از این اعداد رو انتخاب کرد به گونه ای که مجموع اعضای این دو زیر مجموعه برابر باشند!

(راهنمایی: به اصل لانه ی کبوتری ربط داره!!)

 

[RAGA]

پاسخ : آرشیو سوالات از گذشته تا کنون

من جواب نمیدم فقط نظر میدم چون شاید چیزی که میگم بی ربط باشه
10 تا عدد رو به دو مجموعه ی 5 عضوی تقسیم میکنیم:
الف ب
a a-1
b b+1
c c-2
d d+1
e e+1
الان اعضا مشخص شدن ولی باید a,b,c,d,e رو با فاصله از هم انتخاب کنیم
مثلا:{2و5و10و17و20}=ب {1و6و8و18و21}=الف

 

[احسان]

پاسخ : آرشیو سوالات از گذشته تا کنون

یه سوال دیگه:

فرض کنید 10 عدد طبیعی متمایز داریم و همگی این اعداد هم از 107 کوچک ترند! ثابت کنید می شه 2 زیر مجموعه ی مجزا از این اعداد رو انتخاب کرد به گونه ای که مجموع اعضای این دو زیر مجموعه برابر باشند!

(راهنمایی: به اصل لانه ی کبوتری ربط داره!!)

من جواب نمیدم فقط نظر میدم چون شاید چیزی که میگم بی ربط باشه
10 تا عدد رو به دو مجموعه ی 5 عضوی تقسیم میکنیم:
الف ب
a a-1
b b+1
c c-2
d d+1
e e+1
الان اعضا مشخص شدن ولی باید a,b,c,d,e رو با فاصله از هم انتخاب کنیم
مثلا:{2و5و10و17و20}=ب {1و6و8و18و21}=الف

من دقیقاً متوجه منظورت نشدم!

توی این سوال، باید ثابت کنی به ازای هر 10 عددی که داده باشند، دو زیر مجموعه پیدا می شه که مجموع اعضای اون دو زیر مجموعه با هم برابره!! (در ضمن لزومی نداره تعداد اعضای اون دو تا زیر مجموعه با هم برابر باشه!!)