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

[احسان]

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

خب من یه حدسی زدم نمیدونم درسته یا نه :-[
ببینید فرض کنید m>n اون وقت میشه اینطوری برش داد
اول کیک رو به m قسمت برش میدیم.بعد هر کدوم از m-n قسمتش رو به n قسمت برش میدیم.مثلا m=5 و n=3 اعداد هستند.برش ما به این صورت است
اول کیک رابه 5 قسمت برش میدیم.بعد 3-5 قسمت یعنی دوقسمت رو برمیداریم وهرکدوم رو به 3 قسمت تقسیم می کنیم.
حالا اگر 5 نفر بیان که این 5/1 ها رو به هرکدوم میدیم.اگر هم 3 نفر بیاد.از این 5 قسمت به هر نفر یه 5/1 میدیم.بعد دو تا 5/1 میمونه که اول هر کدومش رو به 3 قسمت تقسیم
می کنیم بعد به هر کدوم دو تا از این 3/1 ها میدیم.فهمیدید؟؟؟؟!!!!!
پس به عبارتی تعداد برش ها میشه (اگر n<m)
m+n(m-n)=m+nm-n^2
غلطه نه؟؟؟؟؟!!!

مرسی که روی سوال وقت گذاشتید!

اگه اشتباه نکنم، در روش شما تعداد برش ها برابره با : mn + n - n^2

اول کیک رو به m قسمت تقسیم می کنید! [این می شه m برش] بعدش m - n قسمت رو انتخاب می کنید و هر کدوم رو به n قسمت تقسیم می کنید! [یعنی روی هر کدوم از این m - n قسمت، باید n - 1 برش جدید بزنید! (نه n برش)]

این روش درسته! یعنی با این روش کیک مورد نظر، هم بین m نفر قابل قسمت خواهد بود و هم بین n نفر! ولی روشی وجود داره که تعداد برش هاش از این کمتر باشه!!

منتظر جواب های بهتر هستم!!!! (روش هایی که تعداد برش کمتری نیاز داشته باشن!!)

 

[احسان]

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

باز هم سوال:

یه جدول 10 * 10 داریم که توی هر خونه اش یک نفر داره زندگی می کنه! از این 100 نفر، 9 نفرشون دچار یک بیماری غیر قابل درمان هستند و بقیه سالمند! هر فرد سالمی که حداقل 2 تا از همسایه هاش بیمار باشند، بیمار خواهد شد و به این ترتیب بیماری گسترش پیدا می کنه!! آیا ممکنه همه ی افراد به بیماری آلوده بشن؟!

توضیح: 2 تا خونه وقتی همسایه محسوب می شن که ضلع مشترک داشته باشن! مثلاً هر کدوم از خونه های گوشه ای، 2 تا همسایه دارند!

 

[احسان]

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

سوال:

می خواهیم یک جدول m * n را با 1 و -1 پر کنیم! (یعنی توی هر خونه یا 1 بذاریم یا -1) به طوری که ضرب اعداد هر سطر و همین طور ضرب اعداد هر ستون برابر -1 بشه!

ثابت کنید:

الف) اگه باقیمانده ی m و n بر 2 یکسان نباشه، این کار ممکن نیست

ب) اگه باقیمانده ی m و n بر 2 یکسان باشه، تعداد حالات پر کردن جدول برابره با 2 به توان (m-1)(n-1)

 

[saeed]

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

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

 

[tiberium]

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

می خواهیم یک جدول m * n را با 1 و -1 پر کنیم! (یعنی توی هر خونه یا 1 بذاریم یا -1) به طوری که ضرب اعداد هر سطر و همین طور ضرب اعداد هر ستون برابر -1 بشه!

ثابت کنید:

الف) اگه باقیمانده ی m و n بر 2 یکسان نباشه، این کار ممکن نیست

ب) اگه باقیمانده ی m و n بر 2 یکسان باشه، تعداد حالات پر کردن جدول برابره با 2 به توان (m-1)(n-1)

برای قسمت الف میشه اینطوری گفت
میدونیم که برای اینکه ضرب بشه 1- باید در هر دیف و ستون تعدد فردی 1- داشته باشیم
حالا اگر باقیمانده آن دو بر 2 یکی نباشد یعنی یکی فرد است و دیگری زوج.
حالا اگر بخوایم تعداد 1- ها را در جدول حساب کنیم با تناقض مواجه میشیم چون از یه طرف
فرد *فرد=فرد
زوج*فرد=فرد منظورم رو تونستم برسونم؟

حالا برای قسمت ب)
ردیف اول رو تصور کنید که m خانه داره. خانه ی اول 2 حالت داره,خانه ی دوم همچنین تا خانه ی m-1 یعنی ما میتونیم تو هر کدوم یا 1- بزاریم یا 1 . ولی در خانه ی آخر یا باید 1- بزاریم یا 1 به این علت:
اگر در اون m-1 خانه تعداد 1- فرد باشد,خانه ی آخر هم باید فرد باشد. و اگر تعداد 1- ها زوج باشد خانه ی آخر باید 1- باشد.
برای ستون ها هم همین استدلال را میتوان گفت پس کل حالات میشه 2 به توان (m-1)(n-1)
درستن یا غلط؟؟!!

 

[tiberium]

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

مرسی که روی سوال وقت گذاشتید!

اگه اشتباه نکنم، در روش شما تعداد برش ها برابره با : mn + n - n^2

اول کیک رو به m قسمت تقسیم می کنید! [این می شه m برش] بعدش m - n قسمت رو انتخاب می کنید و هر کدوم رو به n قسمت تقسیم می کنید! [یعنی روی هر کدوم از این m - n قسمت، باید n - 1 برش جدید بزنید! (نه n برش)]

این روش درسته! یعنی با این روش کیک مورد نظر، هم بین m نفر قابل قسمت خواهد بود و هم بین n نفر! ولی روشی وجود داره که تعداد برش هاش از این کمتر باشه!!

منتظر جواب های بهتر هستم!!!! (روش هایی که تعداد برش کمتری نیاز داشته باشن!!)

آها.راست میگید.حواسم نبود که برای تقسیم به n قسمت n-1 برش لازم است!
بازم روش فکر می کنم.ممنون

 

[tiberium]

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

باز هم سوال:

یه جدول 10 * 10 داریم که توی هر خونه اش یک نفر داره زندگی می کنه! از این 100 نفر، 9 نفرشون دچار یک بیماری غیر قابل درمان هستند و بقیه سالمند! هر فرد سالمی که حداقل 2 تا از همسایه هاش بیمار باشند، بیمار خواهد شد و به این ترتیب بیماری گسترش پیدا می کنه!! آیا ممکنه همه ی افراد به بیماری آلوده بشن؟!

توضیح: 2 تا خونه وقتی همسایه محسوب می شن که ضلع مشترک داشته باشن! مثلاً هر کدوم از خونه های گوشه ای، 2 تا همسایه دارند!

من فکر نکنم چنین چیزی ممکن باشه.حداقل باید 10 نفر بیمار باشن.
من الان زیاد وقت ندارم توضیح بدم.ببخشید.ولی امیدوارم بتونم منظورم رو برسونم!
البته استدلالم درپیته!
برای اینکه اون فردی که تو کنجه باید اون دو نفر همسایش بیمار باشن!.
برای این که اون دو نفر بیمار باشن باید اون سه نفر بیمار باشن! یعنی مثلا اگر صفحه شطرنج رو در نظر بگیریم:
برای اینکه کنجیه بیمار بشه(a1) باید a2 و b1 بیمار باشن
برای بیماری این دو باید a3 b2 c1 بیمار باشن.
برای بیماری اینا باید a4 b3 c2 d1 بیمار باشن
و همین طور که پیش بریم بالاخره باید اون 10 خانه ی رو قطر بیمار باشن تا کل خونه ها بیمار بشن چون این کنجی که داریم میگیم یه کنج دیگر هم روبروش هست(یعنی همون کنجی که به وسیله قطر به همین کنج مورد نظر وصل میشه)


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

 

[احسان]

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

برای قسمت الف میشه اینطوری گفت
میدونیم که برای اینکه ضرب بشه 1- باید در هر دیف و ستون تعدد فردی 1- داشته باشیم
حالا اگر باقیمانده آن دو بر 2 یکی نباشد یعنی یکی فرد است و دیگری زوج.
حالا اگر بخوایم تعداد 1- ها را در جدول حساب کنیم با تناقض مواجه میشیم چون از یه طرف
فرد *فرد=فرد
زوج*فرد=فرد منظورم رو تونستم برسونم؟

درسته! همین اثبات رو می شه این جوری هم گفت:

m سطر داریم و ضرب اعداد هر سطر می شه -1 پس ضرب کل اعداد جدول می شه: -1 به توان m
با استدلالی مشابه می شه گفت (چون n ستون داریم و ضرب اعداد هر ستون -1 هست) ضرب کل اعداد جدول می شه: -1 به توان n

یعنی -1 به توان m باید با -1 به توان n برابر باشه!

حالا برای قسمت ب)
ردیف اول رو تصور کنید که m خانه داره. خانه ی اول 2 حالت داره,خانه ی دوم همچنین تا خانه ی m-1 یعنی ما میتونیم تو هر کدوم یا 1- بزاریم یا 1 . ولی در خانه ی آخر یا باید 1- بزاریم یا 1 به این علت:
اگر در اون m-1 خانه تعداد 1- فرد باشد,خانه ی آخر هم باید فرد باشد. و اگر تعداد 1- ها زوج باشد خانه ی آخر باید 1- باشد.
برای ستون ها هم همین استدلال را میتوان گفت پس کل حالات میشه 2 به توان (m-1)(n-1)
درستن یا غلط؟؟!!

یه جورایی درسته! ولی ناقصه!

سطر آخر و ستون آخر رو کنار می ذاریم! برای پر کردن بقیه ی جدول 2 به توان (m-1)(n-1) حالت وجود داره! حالا باید ثابت کنیم خونه های سطر آخر و ستون آخر به صورت یکتا پر خواهند شد!

(ناقص بودن اون راه حل به خاطر اینه که فراموش کردی ضرب اعداد سطر آخر و ستون آخر هم باید -1 بشه!)

 

[احسان]

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

من فکر نکنم چنین چیزی ممکن باشه.حداقل باید 10 نفر بیمار باشن.
من الان زیاد وقت ندارم توضیح بدم.ببخشید.ولی امیدوارم بتونم منظورم رو برسونم!
البته استدلالم درپیته!
برای اینکه اون فردی که تو کنجه باید اون دو نفر همسایش بیمار باشن!.
برای این که اون دو نفر بیمار باشن باید اون سه نفر بیمار باشن! یعنی مثلا اگر صفحه شطرنج رو در نظر بگیریم:
برای اینکه کنجیه بیمار بشه(a1) باید a2 و b1 بیمار باشن
برای بیماری این دو باید a3 b2 c1 بیمار باشن.
برای بیماری اینا باید a4 b3 c2 d1 بیمار باشن
و همین طور که پیش بریم بالاخره باید اون 10 خانه ی رو قطر بیمار باشن تا کل خونه ها بیمار بشن چون این کنجی که داریم میگیم یه کنج دیگر هم روبروش هست(یعنی همون کنجی که به وسیله قطر به همین کنج مورد نظر وصل میشه)


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

این که ممکن نیست همه بیمار بشن، درسته! ولی فکر کنم استدلالت یه کم مشکل داره! (مثلاً ممکنه افراد کنج جدول از اول بیمار باشند!)

 

[احسان]

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

سوال شمارشی نسبتاً آسون:

15 تا صندلی توی یک ردیف چیده شدن و 10 نفر مهمون داریم! به چند حالت مهمون ها می تونند روی صندلی ها بشینند به طوری که دو صندلی خالی کنار هم وجود نداشته باشه؟