حداقل تعداد تلفن ها

math-sina

New Member
ارسال ها
155
لایک ها
52
امتیاز
0
#1
هر یک از اعضای جمعی 55 نفره که همه دوست یکدیگرند، همزمان با بقیه از خبری که با خبرهای بقیه فرق دارد آگاه می شود. این افراد به هم تلفن میکنند تا خبرهایشان را بهم منتقل کنند. هر مکالمه دقیقا یک ساعت طول می کشد و در خلال این مدت هر یک از دو دوست می تواند همه ی اخبارش را به دیگری بگوید. حداقل چند ساعت لازم است که همه ی دوستان از همه ی اخبار مطلع شوند؟ (tt)
 

rezashiri

Well-Known Member
ارسال ها
1,458
لایک ها
325
امتیاز
83
#2
پاسخ : حداقل تعداد تلفن ها

در حالت کلی فکر کنم بشه : 2n-4 !؟

راه حلشم با استقراست!

این سوال مرحله اول دوره 5 المپیاد کامپیوتر بوده!
 
آخرین ویرایش توسط مدیر
ارسال ها
327
لایک ها
378
امتیاز
0
#3
پاسخ : حداقل تعداد تلفن ها

در حالت کلی فکر کنم بشه : 2n-4 !؟

راه حلشم با استقراست!

این سوال مرحله اول دوره 5 المپیاد کامپیوتر بوده!
فک کنم جوب زدید(البته خود من هم زدم :d ) .سوال میگه حداقل.نمیگه با چند بار میشه؟ باید حداقلو بدست آورد:3:
 
آخرین ویرایش توسط مدیر

math-sina

New Member
ارسال ها
155
لایک ها
52
امتیاز
0
#4
پاسخ : حداقل تعداد تلفن ها

دوستان 2n-4 حداکثره !!!
اما سوال حداقل تعداد رو خواسته !
که البته متفاوته !
 
ارسال ها
317
لایک ها
151
امتیاز
0
#5
پاسخ : حداقل تعداد تلفن ها

نه خیر دوستان فک کنم اشتباه میکنید مسئله کتاب دکتر با اون مسئله معروف ttمتفاوته مسئله ttمیگه تو یه ساعت میتونن همه حرف بزنن نه اینکه فقط مکالمه ی 1 نفر با یکی دیگه 1 ساعت طول بکشه تو این حالت میشه فک کنم 5 ساعت اگه درست یادم باشه
64 تا مسئله تورنومنته که میشه حداقلش 6 دور و با یه کارایی میتونید 55 تارو 5 دورش کنید:3:
 
آخرین ویرایش توسط مدیر

math-sina

New Member
ارسال ها
155
لایک ها
52
امتیاز
0
#6
پاسخ : حداقل تعداد تلفن ها

مثلا برای 64 نفر میشه 6 بار تلفن !
(هر دفعه افراد رو به دو دسته تقسیم کنید.)
دقت کنید که 6 خیلی کمتر از
هستش !
 
ارسال ها
327
لایک ها
378
امتیاز
0
#7
پاسخ : حداقل تعداد تلفن ها

دوستان 2n-4 حداکثره !!!
اما سوال حداقل تعداد رو خواسته !
که البته متفاوته !

نه خیر دوستان فک کنم اشتباه میکنید مسئله کتاب دکتر با اون مسئله معروف ttمتفاوته مسئله ttمیگه تو یه ساعت میتونن همه حرف بزنن نه اینکه فقط مکالمه ی 1 نفر با یکی دیگه 1 ساعت طول بکشه تو این حالت میشه فک کنم 5 ساعت اگه درست یادم باشه
درسته دوستان عزیز.جوب خوندنی بود :d
 

math-sina

New Member
ارسال ها
155
لایک ها
52
امتیاز
0
#8
پاسخ : حداقل تعداد تلفن ها

نه خیر دوستان فک کنم اشتباه میکنید مسئله کتاب دکتر با اون مسئله معروف ttمتفاوته مسئله ttمیگه تو یه ساعت میتونن همه حرف بزنن نه اینکه فقط مکالمه ی 1 نفر با یکی دیگه 1 ساعت طول بکشه تو این حالت میشه فک کنم 5 ساعت اگه درست یادم باشه
64 تا مسئله تورنومنته که میشه حداقلش 6 دور و با یه کارایی میتونید 55 تارو 5 دورش کنید:3:
نه از 5 خیلی بیشتره !
 
ارسال ها
317
لایک ها
151
امتیاز
0
#9
پاسخ : حداقل تعداد تلفن ها

البته لازم به ذکره که توی کتاب آقای علیپور اینکه این مقدار حداقل هست رو اثبات نکرده. که البته این هم با استقرا خیلی راحته
نه اون حدقل نیست و اثباتم نمیشده که اثبات نکردن
 
ارسال ها
317
لایک ها
151
امتیاز
0
#11
پاسخ : حداقل تعداد تلفن ها

نه از 5 خیلی بیشتره !
نه ببینید 64 تا رو با 6 تا میشه okکرد باید سعی کنید 55 تارو با 5 تا بچینید احتمالا سوالو بد ترجمه کردین
 

hoco.hc

New Member
ارسال ها
388
لایک ها
267
امتیاز
0
#12
پاسخ : حداقل تعداد تلفن ها

دوستان 2n-4 حداکثره !!!
اما سوال حداقل تعداد رو خواسته !
که البته متفاوته !
مطمئنا 2n-4 حد اکثر نیست. و جالبه بدونید که 2n-4 ( اگه مسئله اون جوری که توی ترکیبیات علیپور هستش باشه ) حداقله.

اگه هم اونجوری که حالا هر کی می گه باشه، جواب فکر کنم بشه
و بعید می دونم برای 55 تا تو 5 ساعت بشه . ( تو 6 ساعت میشه )
 
ارسال ها
317
لایک ها
151
امتیاز
0
#13
پاسخ : حداقل تعداد تلفن ها

نه اشتباه میکنید هر تلفن بین دو نفر یه ساعت زمان نمیبره اینطوریکه سوال بدیهی میشه وقتی جند نفر دوتایی دوتایی باهم صحبت میکنن این یه ساعت وقت میبره نه این که بشینیم ببینیم دونفر یه ساعت حرف زدن حالا دونفر بعدی
 

math-sina

New Member
ارسال ها
155
لایک ها
52
امتیاز
0
#14
پاسخ : حداقل تعداد تلفن ها

نه ببینید 64 تا رو با 6 تا میشه okکرد باید سعی کنید 55 تارو با 5 تا بچینید احتمالا سوالو بد ترجمه کردین
خب 64 چون توانی از 2 هست میشه به این فرم چید.
مثلا برای 3 نفر با 3 بار تلفن میشه اما برای 4 نفر با دو تلفن (چک کردنش خیلی راحته).
55 هم از به مراتب از 5 بیشتره.
اگه خواستین اثبات می کنم.
ترجمه اش هم مال من نیست، برای آقای ارشک حمیدیه.
 

hoco.hc

New Member
ارسال ها
388
لایک ها
267
امتیاز
0
#15
پاسخ : حداقل تعداد تلفن ها

منم با شما هم عقیده ام.با استقرا نمیشه اثبات کرد که این مقدار حداقله.
اگه کتاب مسائل شوروی رو دارید، برید ببینید چند تا اثبات حد اقل بودن رو با استقرا انجام داده.
کی گفته که نمی شه با استقرا حد اقل رو اثبات کرد.
یه عضو خاص رو پیدا میکنیم. و حذفش می کنیم. و می گیم اگه گزاره درست نباشه ، گزاره برای n-1 هم با حذف اون عضو درست نیست.
 
ارسال ها
327
لایک ها
378
امتیاز
0
#16
پاسخ : حداقل تعداد تلفن ها

اگه کتاب مسائل شوروی رو دارید، برید ببینید چند تا اثبات حد اقل بودن رو با استقرا انجام داده.
کی گفته که نمی شه با استقرا حد اقل رو اثبات کرد.
یه عضو خاص رو پیدا میکنیم. و حذفش می کنیم. و می گیم اگه گزاره درست نباشه ، گزاره برای n-1 هم با حذف اون عضو درست نیست.
من نگفتم با استقرا نمیشه حداقل بودن رو ثابت کرد!!!!!!!! :43: من گفتم از نظرم نمیشه واسه این سوال اینکارو کرد!!!
 

hoco.hc

New Member
ارسال ها
388
لایک ها
267
امتیاز
0
#17
پاسخ : حداقل تعداد تلفن ها

من نگفتم با استقرا نمیشه حداقل بودن رو ثابت کرد!!!!!!!! :43: من گفتم از نظرم نمیشه واسه این سوال اینکارو کرد!!!
برای این سوال اثبات می کنیم که یه عضوی وجود داره که حد اکثر دو بار صحبت کرده، حذفش می کنیم، گزاره درست می شه. ( برای n های بزرگ تر از یک ثابت )
 
ارسال ها
317
لایک ها
151
امتیاز
0
#18
پاسخ : حداقل تعداد تلفن ها

خب 64 چون توانی از 2 هست میشه به این فرم چید.
مثلا برای 3 نفر با 3 بار تلفن میشه اما برای 4 نفر با دو تلفن (چک کردنش خیلی راحته).
55 هم از به مراتب از 5 بیشتره.
اگه خواستین اثبات می کنم.
ترجمه اش هم مال من نیست، برای آقای ارشک حمیدیه.
, در هر ساعت هر نفر حد اکثر از 55 خبر آگاه میشه پس میشه 6 تا بله من اشتباهی کردم میشه 6
 
آخرین ویرایش توسط مدیر

hoco.hc

New Member
ارسال ها
388
لایک ها
267
امتیاز
0
#19
پاسخ : حداقل تعداد تلفن ها

, در هر ساعت هر نفر حد اکثر از 4 خبر آگاه میشه پس میشه 6 تا بله من اشتباهی کردم میشه 6
باز هم اشتباهه. در حقیقت باید از 6 بیشتر باشه. ولی لزومی نداره که 6 باشه. ( مگه این که اثبات کنید ) مثل همون 3 که اگه طبق حرف شما باشه، باید با 2 بار صحبت بشه ولی با 3 بار صحبت می شه
 
ارسال ها
317
لایک ها
151
امتیاز
0
#20
پاسخ : حداقل تعداد تلفن ها

خوب برا
استقرا رو nبزنین و با n تا اثبات کنین حالا خیلی راحت یتونید با استقراتون به 6 تای 55 پی ببرید اگه خواستید میشینم براتون میچینم
 
بالا