خبر

[rza]

n نفر (n≥4) را در نظر بگيريد كه هر كدام از آنهادر ابتدا يك خبر جديد را مي داند (خبر ها متمايزند). در هر مرحله دو نفر از اين افراد به هم تلفن مي زنند و تمام اخباري را كه دارند با هم مبادله مي كنند. ثابت كنيد اين افراد مي توانند با 2n-4 بار تلفن زدن از همه اخبار مطلع شوند.

 

[Olympiad]

n نفر (n≥4) را در نظر بگيريد كه هر كدام از آنهادر ابتدا يك خبر جديد را مي داند (خبر ها متمايزند). در هر مرحله دو نفر از اين افراد به هم تلفن مي زنند و تمام اخباري را كه دارند با هم مبادله مي كنند. ثابت كنيد اين افراد مي توانند با 2n-4 بار تلفن زدن از همه اخبار مطلع شوند.

استقرا مي زنيم :

پايه كه معلومه ....

فرض كن براي n=k درست باشه ..... اگه k+1 نفر داشتيم ، ابتدا نفر k+1 ام به يه نفر از بقيه تلفن ميزنه و خبرشو ميگه .... بعد طبق فرض استقرا بقيه با 2n-4 خبر از همه ي خبر ها مطلع ميشن ... در آخر هم يه نفر از اون k نفر به نفر k+1 ام زنگ ميزنه و همه ي خبر ها رو به نفر k+1 ام ميده كه كلا ميشه 2n-2 بار تلفن زدن...پس حكم اثبات شد .....