معما های سخت

[ف ی ز ی ک]

درود
اینم یه سوال جدید:
سوال اينه:
دو تا ليوان داريم. با يه ساختمونه ١٠٠ طبقه.
مي خوايم ببينيم پايين ترين طبقه اي كه اگه ليوانو از اونجا بنداريم ميشكنه، طبقه چندمه.
حالا كمترين تعداد باري كه ميتونيم امتحان كنيم چقده؟

[vahids]

فکر نکردم روش
ولی با دوتا لیوان میشه دوتا طبقه رو تست کرد
بدترین حالت میشه پنجاه بار؟

[ف ی ز ی ک]

ساده ترین کاری که به ذهن میرسه اینه که از طبقه ی اول شروع کنیم به آزمایش تا ببینیم تو کدوم طبقه لیوان میشکنه. که بد ترین حالتش اینه که لیوان تو طبقه ی 100 بشکنه و این جوری شما 100 بار آزمایش کردین. اما این کار به درد نمیخوره. شما باید روشی رو پیشنهاد بدین که در بدترین حالت، کمترین میزان آزمایش رو بخواد تا طبقه ی مطلوب معلوم بشه.
مثلا فرض کنید لیوان اول رو از طبقه ی 20 میندازیم پایین. اگه لیوان نشکست مسلما تو طبقه های 1 تا 19 هم نمیشکنه و باید رو طبقه های 20به بالا آزمایش کنیم. اما اگه لیوان شکست حتما تو طبقه های 20 تا 100 هم میشکنه و ما میتونیم با لیوان دوم از طبقه ی 1تا 19 مجددا آزمایش کنیم تا طبقه ی مطلوب بدست بیاد.
حالا شما روشی رو بگید که در بدترین حالت، با کمترین آزمایش بفهمیم جواب کدوم طبقه است. و چند بار آزمایش در بدترین حالت لازمه؟

فکر نکردم روش
ولی با دوتا لیوان میشه دوتا طبقه رو تست کرد
بدترین حالت میشه پنجاه بار؟

از 50 خیلی کمتره

[sunrise]

ساده ترین کاری که به ذهن میرسه اینه که از طبقه ی اول شروع کنیم به آزمایش تا ببینیم تو کدوم طبقه لیوان میشکنه. که بد ترین حالتش اینه که لیوان تو طبقه ی 100 بشکنه و این جوری شما 100 بار آزمایش کردین. اما این کار به درد نمیخوره. شما باید روشی رو پیشنهاد بدین که در بدترین حالت، کمترین میزان آزمایش رو بخواد تا طبقه ی مطلوب معلوم بشه.
مثلا فرض کنید لیوان اول رو از طبقه ی 20 میندازیم پایین. اگه لیوان نشکست مسلما تو طبقه های 1 تا 19 هم نمیشکنه و باید رو طبقه های 20به بالا آزمایش کنیم. اما اگه لیوان شکست حتما تو طبقه های 20 تا 100 هم میشکنه و ما میتونیم با لیوان دوم از طبقه ی 1تا 19 مجددا آزمایش کنیم تا طبقه ی مطلوب بدست بیاد.
حالا شما روشی رو بگید که در بدترین حالت، با کمترین آزمایش بفهمیم جواب کدوم طبقه است. و چند بار آزمایش در بدترین حالت لازمه؟

فکر نکردم روش
ولی با دوتا لیوان میشه دوتا طبقه رو تست کرد
بدترین حالت میشه پنجاه بار؟

از 50 خیلی کمتره

جواب:با 7 بار(هربار یه لیوان) میشه در بدترین حالت پایینترین طبقه رو پیدا کرد.مثلا در بدترین حالت تو طبقه 100 میشکنه،پس ما اول از طبقه 50 میاندازیم،اگه نشکست از میانگین50و100 یعنی 75 میاندازیم بعد دوباره میانگین87=75و100.بعد 94،بعد 97 بعد98 بعد99.دیگه ازطبقه ی 100نمیندازیم،چون بالأخره تو یه طبقه از ساختمون میشکنه که آخرین طبقه ی باقیمانده برای آزمایش از ساختمونه


این معما رو بیل گیتس در سال 2002 طراحی کرد تا از بین 100 مهندس یکی را برای شرکتش انتخاب کند:

دو اتاق در مجاورت هم قرار دارند.
هر کدام یک در دارند ولی هیچکدام پنجره.ندارند.
درهایشان که بسته باشد درون اتاقها کاملا تاریک است. در یک اتاق سه چراغ برق به توانهای ۱۰۰، ۱۱۰ و ۱۲۰ وات و در اتاق دیگر سه کلید برق مثل هم وجود دارد.

ما نمیدانیم کدام کلید کدام چراغ راروشن میکند( مثلا نمیدانیم آیا کلید وسطی مربوط است به چراغ وسطی یا به چراغهای دیگر اما بطور قطع میدانیم که هر کدام از کلید ها یکی از چراغها را روشن میکند. همچنین ترتیب چراغها را هم نمیدانیم ).

شما معلوم کنید که هر کلید مربوط به کدام چراغ است. برای اینکار و در شروع، شما باید در اتاق کلیدها باشید و کار را از آنجا شروع کنید.

شما میتوانید هر چند مرتبه که بخواهید کلیدها را روشن و خاموش کنید. اما شما تنها هستید و نمیتوانید از کسی کمک بگیرید و هیچگونه وسیله ای هم خواه برقی خواه غیر برقی بهمراه ندارید و مهمتر از همه اینکه شما حق ندارید بیش از یکبار وارد اتاق چراغها شوید و وقتیکه وارد شدید و بیرون آمدید، دیگر نمیتوانید مجددا وارد آن اتاق بشوید.

حال پیدا کنبد که هر کلید کدام چراغ را روشن می کند؟

[You-See]

من می دونم ولی برای این که بی مزه نشه نمی گم

[اشکان فیاض]

یکی از کلید ها را میزنیم تابرای چند دقیقه لامپ روشن باشد و گرم شود بعد انرا خاموش و کلید دیگری را میزنیم بعد به اتاق لامپ ها میرویم لامپی که روشن بود مربوط به کلیدی است که بار دوم زدیم از بین لاپ های خاموش اونی که گرم بود مربوط به کلیدی است که ابتدا روشن و بعد خاموش کردیم و لامپ سوم هم ماله کلیدیه که دست نزدیم بهش درسته؟؟

[ف ی ز ی ک]

جواب:با 7 بار(هربار یه لیوان) میشه در بدترین حالت پایینترین طبقه رو پیدا کرد.مثلا در بدترین حالت تو طبقه 100 میشکنه،پس ما اول از طبقه 50 میاندازیم،اگه نشکست از میانگین50و100 یعنی 75 میاندازیم بعد دوباره میانگین87=75و100.بعد 94،بعد 97 بعد98 بعد99.دیگه ازطبقه ی 100نمیندازیم،چون بالأخره تو یه طبقه از ساختمون میشکنه که آخرین طبقه ی باقیمانده برای آزمایش از ساختمونه

سلام این روش ایراد داره.
فرض کنیم لیوان تو طبقه ی 50 شکست. طبق روش شما باید لیوان دوم رو در طبقه ی 25 رها کنیم. خوب اگه اون جا هم لیوان شکست چی؟ هر دو تا لیوان شما شکسته و جواب معلوم نشده.
چون هر یک از طبقات 1 تا 25 میتونه جواب باشه.

[mmeftahpour]

باسلام
نمی دونم استراتژی من بهترین حالت هست یا نه ولی با این روش بدترین جواب 19 بار میشه.
چون دو تا لیوان داریم؛ حداکثر دو بار فرصت شکست در تست رو داریم. ساده ترین روش اینه که از طبقه اول شروع کنیم بریم بالا که میشه 100 بار ولی اشکال این روش اینه که از فرصت دوم استفاده نمی کنیم.
می تونیم از طبقه دوم شروع کنیم بریم بالا. اگر لیوان نشکست ؛ دو طبقه بریم بالا و اگر شکست طبقه پایین رو امتحان کنیم. میشه 51 بار
حالا از طبقه n ام شروع کنیم. اگر نشکست n طبقه بریم بالا و اگر شکست از یک طبقه بالاتر از طبقه ایی که نشکسته بود شروع کنیم بیایم بالا.
مثلا اگر 4 تا 4 تا بریم جلو 4و8و12و16 رو تست می کنیم و اگر تو طبقه 16 شکست از طبقه 9 شروع می کنیم میایم بالا.
با جدول زیر اگر با پرش های 8 تایی بریم جلو میشه 19 بار.

P24.jpg

البته با 9و10و11و12و13 هم همین نتیجه 19 بار بدست میاد.
ولی واقعا لیوانهای پر رویی هستند که نمیشکنن - لیوانهای ما از فاصله یک متری می افته میشکنه.

[jhvh]

منم همین جواب رو داده بودم و گفته بودم حول و حوش بیست بار
اما پاکش کردن

[jhvh]

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

[sunrise]

یکی از کلید ها را میزنیم تابرای چند دقیقه لامپ روشن باشد و گرم شود بعد انرا خاموش و کلید دیگری را میزنیم بعد به اتاق لامپ ها میرویم لامپی که روشن بود مربوط به کلیدی است که بار دوم زدیم از بین لاپ های خاموش اونی که گرم بود مربوط به کلیدی است که ابتدا روشن و بعد خاموش کردیم و لامپ سوم هم ماله کلیدیه که دست نزدیم بهش درسته؟؟

آفرین اشکان، تو شرکت بیل گیتس استخدامی

[sunrise]

همه خسته نباشید.
این معمای جالب لیوانها(از:ف ی ز ی ک)رو خیلی جیگرکی حل کردید.


معما:تعداد نامعلومی از هواداران فوتبال میخواهند نتیجه ی تمام 7 بازی(مسابقه)تیم ملی تو یه تورنمنتی رو(مثلا انتخوابی جام جهانی آسیا در گروهی 8تیمی) پیشگویی کنند؛(پیشگویی: برد،تساوی یاباخت)به طوری که بعد از اتمام تمام بازیهای تیم ملی یه نفر به احتمال "صد در صد" همه ی بازیهای تیم ملی رو درست پیشگویی کرده باشه.
حالا دو سوال:
1-این افراد با چه روشی بازیها رو پیشگویی میکنند؟
2-تعداد این افراد چند نفر باید باشد؟

(نکته ها:
1-هیچ نکته ی انحرافی ای وجود ندارد و با فرمول خاصی سوالها قابل حل اند.
2-هیچ بازی ای در صورت تساوی در 90 دقیقه به ضربات پنالتی یا 30دقیقه وقت اضافه کشیده نمیشود.)

[ف ی ز ی ک]

سلام به mmeftahpour و jhvh
19 جواب درسته. جالبه بدونید که این سوالو یه شرکت آمریکایی برای مصاحبه در استخدام، از متقاضیان پرسیده.شبیه کاری که بیل گیتس در سال 2002 انجام داده.
گویا نظر طراح سوال این بوده که جوابش 19 میشه.
اما به نظر من جواب 18 است. چون طبق جدول آقای mmeftahpour در حالت n=10 نیازی نیست که در طبقه ی 100 آزمایش انجام دهیم. چون مسلما لیوان در این طبقه میشکنه. و تعداد آزمایش ها میشود 18.
البته بدون کشیدن جدول و انجام آزمون و خطا هم میشود سوال رو حل کرد. کافیه شما یه تابع بر حسب n معرفی کنید که تعداد کل آزمایش هارو نشون بده. اگر مشتق این تابع رو مساوی صفر قرار دهید، n بدست میاد 10. و با جا گذاری 10 در تابع تعداد حالت 19 یا 18 است. اگر شما لیوان دوم رو در طبقه 100 هم رها کنید جواب 19 است. و اگر این کار را نکنید تابع شما یه 1-
هم داره و در این صورت جواب 18 است.

[mmeftahpour]

ما به نظر من جواب 18 است. چون طبق جدول آقای mmeftahpour در حالت n=10 نیازی نیست که در طبقه ی 100 آزمایش انجام دهیم. چون مسلما لیوان در این طبقه میشکنه. و تعداد آزمایش ها میشود 18.

تا طبقه 100 باید 10 بار تست کنیم - اگر در طبقه 100 شکست دوباره باید از طبقه 91 الی 99 رو تست کنیم (میشه 9 بار)
مجموعا میشه 19 بار

[mmeftahpour]

معما:تعداد نامعلومی از هواداران فوتبال میخواهند نتیجه ی تمام 7 بازی(مسابقه)تیم ملی تو یه تورنمنتی رو(مثلا انتخوابی جام جهانی آسیا در گروهی 8نفره) پیشگویی کنند؛(پیشگویی: برد،تساوی یاباخت)به طوری که بعد از اتمام تمام بازیهای تیم ملی یه نفر به احتمال "صد در صد" همه ی بازیهای تیم ملی رو درست پیشگویی کرده باشه.
حالا دو سوال:
1-این افراد با چه روشی بازیها رو پیشگویی میکنند؟
2-تعداد این افراد چند نفر باید باشد؟

(نکته:هیچ نکته ی انحرافی ای وجود ندارد و با فرمول خاصی سوالها قابل حل اند.)

تعداد 7 بازی است و هر بازی 3 حالت دارد. (مستقل از نتیجه دیگر بازیها) پس تعداد حالت ممکن میشه 7^3 (2187) حالت. پس ما حداقل به 2187 نفر احتیاج داریم.
روشش هم باید همه حالتها رو بنویسیم. چون تعداد زیاده بهتره یک برنامه کامپیوتری بنویسیم.
بجای برد،تساوی یاباخت 2و1و0 در نظر می گیریم/ حالا نفر اول یک عدد هفت رقمی دارد. (7 تا صفر یا 7 تا باخت 0000000)
برای نفر بعدی یک اضافه می کنیم میشه 0000001 - نفر بعدی 0000002
نفر بعدی میشه 0000003 ولی خوب ما 3 نداریم (دقیقا مثل سیستم دهدهی با 3 برخورد می کنیم - در واقع عددمون در مبنای 3 هست)
پس میشه 0000010 و همینطور ادامه میدیم.
0000000
0000001
0000002
0000010
0000011
0000012
0000020
0000021
0000022
0000100
.
.
.
2222220
2222221
2222222