سوال اکسترمال رو با استقرا حل کنید.
پاسخ : سوال اکسترمال رو با استقرا حل کنید.
متن دقیق سوال اینه(مرحله دو سال 2006 روز اول)
[TABLE="width: 100%"]
[TR="class: res_gen"]
[TD="class: row1"]In the night, stars in the sky are seen in different time intervals. Suppose for every
stars (
), at least
of them can be seen in one moment. Prove that we can photograph
pictures from the sky such that each of the mentioned stars is seen in at least one of the pictures.
(The number of stars is finite. Define the moments that the
star is seen as
that
.) [/TD]
[TD="align: center"] [/TD]
[/TR]
[TR]
[TD="colspan: 3"] [/TD]
[/TR]
[/TABLE]
متن دقیق سوال اینه(مرحله دو سال 2006 روز اول)
[TABLE="width: 100%"]
[TR="class: res_gen"]
[TD="class: row1"]In the night, stars in the sky are seen in different time intervals. Suppose for every
(The number of stars is finite. Define the moments that the
[TD="align: center"] [/TD]
[/TR]
[TR]
[TD="colspan: 3"] [/TD]
[/TR]
[/TABLE]
پاسخ : سوال اکسترمال رو با استقرا حل کنید.
یا من سوالو اشتبا فهمیدم یا سوال اصن اکسترمال و استقرا اینا نیست بلکه خیلی ساده تره:
این الگوریتم رو ارائه میدم:
تو لحظه ی اول عکس بگیر
تو هر لحظه ای که یه ستاره ای تو آسمون بود که قبلن تو عکس هات نبود، عکس بگیر
ادعا میکنم پس از k - 1 عکس، همه ی ستاره ها تو عکس ها اومدن
پس از عکس اول، k - 2 ستاره هستن که تو عکس ها نیومدن و با هر عکس حداقل یکی از اون ها تو عکس ها میاد (چون هر ستاره حداقل یه لحظه تو آسمون پیدا میشه)
پس با مجموعن k - 1 عکس ، همه ی ستاره ها رو میبینیم.
یا من سوالو اشتبا فهمیدم یا سوال اصن اکسترمال و استقرا اینا نیست بلکه خیلی ساده تره:
این الگوریتم رو ارائه میدم:
تو لحظه ی اول عکس بگیر
تو هر لحظه ای که یه ستاره ای تو آسمون بود که قبلن تو عکس هات نبود، عکس بگیر
ادعا میکنم پس از k - 1 عکس، همه ی ستاره ها تو عکس ها اومدن
پس از عکس اول، k - 2 ستاره هستن که تو عکس ها نیومدن و با هر عکس حداقل یکی از اون ها تو عکس ها میاد (چون هر ستاره حداقل یه لحظه تو آسمون پیدا میشه)
پس با مجموعن k - 1 عکس ، همه ی ستاره ها رو میبینیم.
