حداقل تعداد تلفن ها
پاسخ : حداقل تعداد تلفن ها
من یه نیم ساعت فک کردم و به این نتایج رسیدم (پیج های قبلی رو نخوندم شاید شما قبلن به اینا رسیدین )
به ازای n ای فرض میکنیم n=2^k +s که در اینجا s <2^k خوب حالا n نفررو به دوگروه s تایی و 2^k تایی تقسیم کنین و در ساعت اول s نفر رو به s نفر از گروه دوم وصل کنید .(تماس بگیرن) حالا همه ی خبر ها در گروه 2^k وجود دارد به وضوح هم این خبر ها رو در k ساعت میتوان به تمام افراد گروه 2^k تایی رساند . حالا بار دیگری افراد گروه دیگر(اون s نفره رو ) مانند حرکت اول به s نفر از گروه 2^k وصل کنین ودر این حالت با k+2 تماس همه از خبر ها با خبرند . (همچنین به وضوح همون طور که دوستان اشاره کردن حداقل k+1 تا لازمه )
برای 55 هم میتوان اثبات کرد با 6 تا نمیشه اما نتونستم برای n های کلی تعمیمش بدم .
من یه نیم ساعت فک کردم و به این نتایج رسیدم (پیج های قبلی رو نخوندم شاید شما قبلن به اینا رسیدین )
به ازای n ای فرض میکنیم n=2^k +s که در اینجا s <2^k خوب حالا n نفررو به دوگروه s تایی و 2^k تایی تقسیم کنین و در ساعت اول s نفر رو به s نفر از گروه دوم وصل کنید .(تماس بگیرن) حالا همه ی خبر ها در گروه 2^k وجود دارد به وضوح هم این خبر ها رو در k ساعت میتوان به تمام افراد گروه 2^k تایی رساند . حالا بار دیگری افراد گروه دیگر(اون s نفره رو ) مانند حرکت اول به s نفر از گروه 2^k وصل کنین ودر این حالت با k+2 تماس همه از خبر ها با خبرند . (همچنین به وضوح همون طور که دوستان اشاره کردن حداقل k+1 تا لازمه )
برای 55 هم میتوان اثبات کرد با 6 تا نمیشه اما نتونستم برای n های کلی تعمیمش بدم .
پاسخ : حداقل تعداد تلفن ها
به hoco.hc :
من برای تمام m ها نگفتم جواب برابر با k+2 میشه و تنها نشون دادم برای تموم حالت ها با k+2 بار میتوان حکم را برقرار کرد .
حالا بدیهیه که برای M فرد با k+1 بار نمیشه حکم را برقرار کرد چون در هر مرحله اطلاعات هر فرد حداکثر 2 برابر میشه پس در مرحله k ام اطلاعات هر فرد حداکثر برابر با 2^k است و به وضوح میدانیم در مرحله k+1 ام حداقل یک فرد است که با کسی مکالمه نمیکند این فرد در مرحله ی k+1 ام هم حداکثر 2^k اطلاعات دارد و پس حداقل یک مکالمه ی دیگر باید صورت بگیرد که میشود k+2 مرتبه .
به hoco.hc :
من برای تمام m ها نگفتم جواب برابر با k+2 میشه و تنها نشون دادم برای تموم حالت ها با k+2 بار میتوان حکم را برقرار کرد .
حالا بدیهیه که برای M فرد با k+1 بار نمیشه حکم را برقرار کرد چون در هر مرحله اطلاعات هر فرد حداکثر 2 برابر میشه پس در مرحله k ام اطلاعات هر فرد حداکثر برابر با 2^k است و به وضوح میدانیم در مرحله k+1 ام حداقل یک فرد است که با کسی مکالمه نمیکند این فرد در مرحله ی k+1 ام هم حداکثر 2^k اطلاعات دارد و پس حداقل یک مکالمه ی دیگر باید صورت بگیرد که میشود k+2 مرتبه .
پاسخ : حداقل تعداد تلفن ها
مثل این که یه سری از بچه ها منظورم رو نهمیدن :
منظور من از این که مشابه m های فرد عمل کنید این بود که سعی کنید الگوریتمی بدید که تو هر اطلاعات هر فرد را به مقدار کافی افزایش بده .
اما میتونید استقرایی هم عمل کنید . واسه استقرا کافیه برای اعداد به شکل 2p که p عدد فردی است حکم رو اثبات کنید .
برای اینم که کافیه دو گروه p تایی تقسیم کنید میدانیم هر کدام از گروه های p تایی در سقف lg p +1 مرحله از تمام اطلاعات یکدیگر با خبر میشن حالا تو هر ساعت دو فرد در دو گروه که مالمه ای انجام نمیدن (که میدونیم وجود داره) رو به هم وصل کنین در این صورت بعد از همان سقف lg p+1 ساعت همه ی 2p نفر از اطلاعات همدیگر با خبر میشن که همون حکم مسئله برای m های زوجه .
مثل این که یه سری از بچه ها منظورم رو نهمیدن :
منظور من از این که مشابه m های فرد عمل کنید این بود که سعی کنید الگوریتمی بدید که تو هر اطلاعات هر فرد را به مقدار کافی افزایش بده .
اما میتونید استقرایی هم عمل کنید . واسه استقرا کافیه برای اعداد به شکل 2p که p عدد فردی است حکم رو اثبات کنید .
برای اینم که کافیه دو گروه p تایی تقسیم کنید میدانیم هر کدام از گروه های p تایی در سقف lg p +1 مرحله از تمام اطلاعات یکدیگر با خبر میشن حالا تو هر ساعت دو فرد در دو گروه که مالمه ای انجام نمیدن (که میدونیم وجود داره) رو به هم وصل کنین در این صورت بعد از همان سقف lg p+1 ساعت همه ی 2p نفر از اطلاعات همدیگر با خبر میشن که همون حکم مسئله برای m های زوجه .