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

[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 عددی که داده باشند، دو زیر مجموعه پیدا می شه که مجموع اعضای اون دو زیر مجموعه با هم برابره!! (در ضمن لزومی نداره تعداد اعضای اون دو تا زیر مجموعه با هم برابر باشه!!)

 

[RAGA]

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

ببخشید من اعضای مجموعه رو خودم انتخاب کردم.

 

[armita]

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

اين ١٠ عدد ١٠٢٤ تا زير مجموعه دارن، كه مجموع بزرگترين زير مجموعه ١٠١٥ است(١٠٦+١٠٥+١٠٤+...+٩٧)
چون تعداد زير مجموعه ها بيشتره پس طبق اصل لانه كبوتري ٢ زير مجموعه هستن كه مجموع اعضاشون برابره.اگر اين ٢ مجموعه عضو يكسان نداشته باشن حكم اثبات مي شه، اگر هم عضو يكسان داشته باشن اعضاي يكسان رو از هر دو مجموعه برمي داريم و باز حكم اثبات مي شه!

 

[احسان]

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

یه سوال دیگه:

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

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

اين ١٠ عدد ١٠٢٤ تا زير مجموعه دارن، كه مجموع بزرگترين زير مجموعه ١٠١٥ است(١٠٦+١٠٥+١٠٤+...+٩٧)
چون تعداد زير مجموعه ها بيشتره پس طبق اصل لانه كبوتري ٢ زير مجموعه هستن كه مجموع اعضاشون برابره.اگر اين ٢ مجموعه عضو يكسان نداشته باشن حكم اثبات مي شه، اگر هم عضو يكسان داشته باشن اعضاي يكسان رو از هر دو مجموعه برمي داريم و باز حكم اثبات مي شه!

درسته!

پی. اس. چون چندین سوال حل نشده مونده، هر سوالی رو که خواستید جواب بدید، بگید جواب کدوم سواله!! (برای سوال های حل شده هم اگه ایده های دیگه ای دارید بگید!! )

 

[armita]

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

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

 

[hshkhkh]

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

******ولی حتی اگر یه نفر اشتباه دستشو ببره بالا همه اعدام می شن .********
خوب این یعنی چی؟

 

[armita]

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

یعنی اگر پادشاه گفته چشم آبی ها دستاتون رو بیارین بالا یک چشم سبز دستشو ببره بالا همه اعدام می شن.

 

[tiberium]

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

خب!!

یه راه بهتر پیدا کردم.اون یکی غلط نیست ولی یکم پیچه!!

ولی تو این راه اینا زودتر آزاد میشن.!!

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

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

و فردا که شاه بیاد اینو بپرسه هر سه تایی دست بلند می کنیم چون با این استدلال بالا فهمیدیم که چشممون آبیه.

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

اینو تعمیمش میدیم.و با این وضع مساله حل میشه.

 

[tiberium]

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

الان مثلا فرضا دو نفر a و b چشماشون آبیه
شاه روز اول میگه چشم آبیا دستشون بالا
نفر a میبینه که چشم b آبیه.
و b هم میبینه که چشم a آبیه.
و هردوتاشون هم میبینن که چشم مابقی سبز هست

حالا مثلا چون نفر a میبینه که چشم b آبیه پس نمیتونه بفهمه چشمش چه رنگیه.
و نفر b هم همچنین.یعنی نمیفهمه چشمش چه رنگیه.
و روز اول کسی دست بلند نمی کنه.
حالا فرداش که شاه دوباره میگه چشم آبیا دستشون بالا نفر a اینطوری استدلال می کنه.
میگه رنگ چشم بقیه زندانیا به جز b همه سبزه.
اگر چشم منم سبز بود b میفهمید که چشمش باید آبی باشه.ولی وقتی دست بلند نکرده یعنی نفهمیه
پس چشم من حتما آبیه.
b هم همین استدلال رو می کنه.پس روز دوم هر دو دستشون رو میبرن بالا.

 

[tiberium]

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

حالا فرض کنیم سه نفر چشماشون آبیه
a
b
c

خب روز اول شاه میاد میگه چشم آبیا دستشون بالا
a میبینه چشم دو نفر (b,c) آبیه.پس نمیفهمه چشم خودش چه رنگیه
b هم همینطور
c هم همینطور

پس روز اول دستی بلند نمیشه

حالا روز دوم میشه.
شاه دوباره میپرسه چشم آبیا دستشون بالا

حالا:
فرضا من نفر a هستم.
من میدونم b و c چشمشون آبیه.
اگر چشم من سبز بود پس وقتی امروز شاه میگه دست چشم آبیا بالا پس اینا میفهمیدن که چشمشون آبیه و دستشون رو میبردن بالا.
من وقتی دوباره کسی دستش رو نمیبره بالا یعنی حتما چشم من آبیه.
چون در غیر این صورت(یعنی اگر چشم من سبز بود) این دو نفر تو روز دوم(یعنی امروز) دستشون رو میبردن بالا.
حالا که نبردن یعنی چشمم آبیه.

هر سه نفر همزمان این استدلال رو می کنن.
پس فرداش یعنی روز سوم که پادشاه بگه چشم آبیا دستشون بالا هر سه تا دستشون رو بلند می کنن

 

[tiberium]

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

حالا چهار نفر رو هم بگیم بعد دیگه خودتون تعمیم بدید!!!
a
b
c
d
چشماشون آبیه.
روز اول که شاه میگه چشم آبیا دستشون بالا کسی دست بلند نمیکنه چون میبینه چشم سه نفر دیگه آبیه.
روز دوم هم کسی دست بلند نمیکنه.
روز سوم هم همچنین

حالا فرض می کنم من a هستم
با خودم اینطوری استدلال می کنم
اگر فقط چشم های b c d آبی باشه
با توضیحات قبل! اینا تو روز سوم متوجه میشن و دستشون رو میبرن بالا.!! حالا چون دستشون رو نبردن بالا پس چشم من حتما آبیه.

هرکدوم این استدلال رو می کنن.

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