به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+4 امتیاز
1,088 بازدید
در دبیرستان توسط Taha1381 (1,789 امتیاز)
ویرایش شده توسط Taha1381

مریخی در نیمه شب متولد می شود و درست ۱۰۰ شببانه روز زندگی می کند.می دانیم در طول تاریخ تمدن مریخ روی هم به تعداد فردی مریخی به دنیا امده است.ثابت کنید حداقل ۱۰۰ روز وجود دارد که تعداد ساکنان مریخ در هر یک از این روز ها عددی فرد بوده است.(المپیاد ریاضی لینگراد۱۹۸۶)

من حل رو نمی خوام فقط مفهموم سوال رو نفهمیدم و می خوام برام مفهومش کنید

صورت اصلی سوال از ترکیبیات دکتر علیپور:

enter image description here

جواب سوال از کتاب ترکیبیات علیپور:

enter image description here

صورت اصلی سوال از کتاب المپیاد های ریاضی لینگراد:

enter image description here

جواب سوال از کتاب المیاد های ریاضی لینگراد:

enter image description here

مرجع: ترکیبیات(دکتر علیپور)
توسط AmirHosein (19,718 امتیاز)
اگر بتوانید پیوندی یا هر گونه ارجاعی به متن اصلی خود پرسش در المپیاد یادشده بگذارید بسیار عالی می‌شود.

نکتهٔ یکم این پرسش که باید به آن دقت کنید این است که پرسش‌گر گفته‌است در هر شبانه‌روز دقیقا در یک زمان ثابت تولدها صورت می‌گیرند و مرگ‌ها خودکار و پس از گذراندن ۱۰۰ روز کامل صورت می‌گیرد. این دو با یکدیگر یعنی جمعیت در طول ۲۴ ساعت شبانه‌روز عددی ثابت است و این به شما اجازه می‌دهد که تابع جمعیت، تابع میزان تولد و تابع میزان مرگ و میر را بر حسب متغیر تعداد روز سپری شده از مبدأ زمان بنویسید و با تابع‌های گسسته سر و کار داشته‌باشید (برای نمونه دیگر با یک تابع پیوسته سر و کار ندارید). پس پرسش معنادار نیز است.

نکتهٔ دیگر اینکه، در هر جای زمان بایستید، تابع تجمعی میزان زاد و ولد یعنی جمع تعداد تولدهای صورت‌گرفته در روز یکم تا روزی که در آنجا هستید، عددی فرد است. این به این معنا نیست که هر روز تعداد فردی تولد دارید! بلکه یعنی جمع تعداد تولدهای همهٔ روزها تا اینجا عددی فرد است.  از اینجا می‌توانید نتیجه بگیرید که روز یکم تعداد فردی تولد بوده‌است. روز دوم اتفاقا برعکس باید تعداد زوجی تولد داشته باشید و گرنه جمع دو عدد فرد، عددی زوج است! به طریق مشابه با یک استقراء از نوع گام دوم، تعداد تولدها در هر روز غیر از روز یکم عددی زوج است. برای نمونه می‌تواند فراوانی‌های نسبی روزها به این شکل باشد ۳، ۲، ۴، ۲، ۶، ۱۰، ۲، ...

اکنون توجه کنید که از روز یک تا روز ۱۰۰ هیچ مرگی هنوز روی نداده است (در خود روز صدم، متولدین روز یکم، نود و نه روزه‌ هستند) و فقط با تولد روبرو هستیم. پس جمعیت در روز n که n کمتر یا مساوی ۱۰۰ است برابر با جمع تعداد تولدها از روز یک تا روز n است که همان تابع تجمعی تولد است و می‌دانیم که فرد است. اما اکنون قسمت جالب اینجا است که روز صد و یکم زوج عدد به دنیا می‌آیند و فرد عدد (دقیقا تعداد افرادی که در روز یکم به دنیا آمده‌اند) از دنیا می‌روند که برآیند آنها یک عدد مثبت یا منفی ولی فرد است. جمع این عدد (مثبت یا منفی) فرد با جمعیت روز صدم که عددی فرد بود، عددی زوج می‌شود! پس روز صد و یکم با جمعیت زوج روبرو شدیم! روز صد و دوم زوج تا به دنیا می‌آیند و زوج تا می‌میرند (چون روز دوم زوج‌تا به دنیا آمده‌بودند. که برآیندش زوج است و جمع زوج (مثبت یا منفی) با جمعیت روز پیشین که زوج بود عددی زوج می‌دهد و این روند تا آخر اینگونه است یعنی تا آخر جمعیت زوج است و تنها ۱۰۰ روز نخست تنها ۱۰۰ روزی هستند که به پرسش‌گر می‌توانیم بدهیم.

اما در بحثی که کردیم فرض این بود که در شروع زمان (شروع روز یکم) جمعیت صفر بوده‌است و تولد خلق‌الساعه‌ای داشته‌ایم. به همین دلیل این مطلب پاسخی که پرسش‌گر می‌خواسته‌است نیست و به شکل دیدگاه قرار دادم. در ضمن از آنجا که یک ریاضی‌دان معتبر پرسش را طراحی کرده‌است برای واژهٔ «دست‌کم» دلیل داشته‌است! هیچ‌گاه یک ریاضی‌دان حرفه‌ای واژه‌ای را بی‌دلیل اضافه یا کم نمی‌کند، در ضمن تأکیدی بر خواستن این ۱۰۰ روز به شکل پشت‌سرهم و متوالی انجام نداده‌است و این نیز باید دلیل داشته‌باشد.

امیدوارم پرسش برایتان روشن شده‌باشد.
توسط Taha1381 (1,789 امتیاز)
+1
اینو از کتاب ترکیبیات علیپور برداشتم اما تو منبع نوشته المپیاد های ریاضی لینگراد۱۹۸۶ کتابشو می تونید ازhttp://www.irysc.com/forum/t8123/ برش دارید.عکسشو سعی می کنم بزارم.
توسط Taha1381 (1,789 امتیاز)
ببخشید مال سال ۱۹۸۶ هستش اشتباه نوشتم(:

2 پاسخ

+1 امتیاز
توسط A Math L (2,400 امتیاز)
ویرایش شده توسط A Math L
 
بهترین پاسخ

هر مریخی 100 روز عمر میکنه . در کل هم تعداده مریخی هایی که متولد شدن فرد بوده . باید ثابت کنیم در طول تاریخ تمدن مریخ 100 روز وجود داره که تعداد مریخی هایی که تو اون روزا زنده بودن تعدادی فرده . سوال رو خیلی نمیتونم توضیح بدم . یه تاریخ در نظر بگیر 100 روز داره . هرکس که به دنیا میاد تو همه روز های این تاریخ زندگی میکنه . مثلا اگه ینفر تاریخ دهم بدنیا بیاد تا تاریخ نهم دور بعد زنده میمونه.

هر 100 روز مریخ رو یک سال مینامیم . میدانیم هر فردی که به دنیا میاد در همه روز های سال زندگی میکنه . حال ما روز n رو در نظر میگیریم $( 1 \leq n \leq 100 )$. میدانیم تعداد افرادی که در تاریخ n ام سال های متفاوت زندگی کردن برابر تعداد کل افراده چون هر فردی که به دنیا اومده در تاریخ nام زنده بوده . چون تعداد کل افراد فرده پس تعداد کسایی که تو روزهای nام سال های متفاوت بودن هم ، فرده پس حداقل یک سال بوده که روز nامش تعدادی فرد آدم زنده بودن . n میتونه اعداد 1 تا 100 باشه و در هرکدوم حداقل یک روز هست که تعداد افرادش فرد هستند پس در کل حداقل 100 روز با این ویژگی وجود داره .

توسط AmirHosein (19,718 امتیاز)
من که ثابت شدن چیزی را در این پاسخ نمی‌بینم. «یک تاریخ در نظر بگیر، ۱۰۰ روز دارد» در کل جمله‌ای بی‌معنا است! منظورتان این است که یک فرد مریخی را در نظر بگیرید، ۱۰۰ روز عمرش است. خب؟ یک روز را در نظر می‌گیریم. هر مریخی‌ای که در این روز به دنیا می‌آید تا ۱۰۰ روز دیگر زنده‌است، خب دنباله‌اش چه؟ فردای آن روز نیز مریخی به دنیا می‌آید! پیش از آن روز نیز همین‌گونه، بیشتر روی پرسش فکر کنید.
توسط A Math L (2,400 امتیاز)
چون نوشته بود راه حل نیاز نیست من کامل ننوشته بودم الان کامل شد .
توسط AmirHosein (19,718 امتیاز)
چیزی که شما نوشتید یعنی هر روز تعداد مریخی‌ها فرد است که درست نیست! بر فرض یک سال ۱۰۰ روز باشد، شما (فرض کنیم پاسخ شما درست باشد) ثابت می‌کنید که هر روز سال تعداد فردی مریخی وجود دارد که در نتیجه یعنی همهٔ روزهای سال که این سال شما یک سال دلخواه بدون هیچ شرطی است، پس در تمام روزها بدون وابستگی به سال، یعنی همیشه تعداد مریخی‌ها فرد است.
توسط A Math L (2,400 امتیاز)
نه درسته . منظورمو درست متوجه نشدید . روز nام همه سال هارو در نظر بگیرید تعداد افرادی که تو روز nام همه سال ها مثلا روز دوم همه سال ها با هم ، زنده بودن برابر تعداد کل افراد چون اگه فردی تو یه سال متولد بشه یک روز از عمرشو تو تاریخ nام میگذرونه . چون این تعداد فرده پس حد اقل یک روز در تاریخ n شامل تعداد فرد مریخی بوده .
توسط AmirHosein (19,718 امتیاز)
دیدگاه آخرتان هیچ توضیحی به حرف‌های پیشینتان (دست‌کم زمانی که من می‌خوانم) نیافزود. خیلی متن شما را دوباره از نو می‌خوانم چه پاسختان و چه دیدگاه‌هایتان ولی هیچ تفاوتی نمی‌کند. کاملا مبهم است. امیدوارم ناراحت نشوید، هدف بحث ریاضی است و با در نظر گرفتن داشتن ظرفیت آکادمی راحت بهتان نظرم را می‌گویم.
توسط A Math L (2,400 امتیاز)
+1
قبول دارم توضیحاتم پیچیدس . چیزیه که نمیتونم درست بیانش کنم یا حداقل بنویسمش . تو این جواب اثبات میشه که طی تاریخ مریخ ، تاریخ یکمه حداقل یک سال شامل تعداد فرد مریخی بوده چون اگه تاریخ یکم همه سال ها شامل تعداد زوج مریخی باشه اونوقت تعداد تمام مریخی هایی که متولد شدن زوجه چون تعداد کسایی که تو تاریخ یکم ( یکمه تمامی سال ها ) زندگی کردن با تعداد کل افراد برابره . تاریخای دیگم به همین صورت . اینم مثل همونا شد ولی گفتم شاید کمکی بکنه .
توسط AmirHosein (19,718 امتیاز)
ویرایش شده توسط AmirHosein
دیدگاهی که برای خود پرسش نوشتم را نگاهی بیندازید. چیزی که از پرسش به شکل نوشته‌شده در بالا در نگاه نخست، دستگیر من می‌شد را برایتان نوشتم. می‌توانید در بیان دقیق ایده‌تان از روش توضیح‌دادنم یاری بگیرید. اگر هم چیزی از پرسش هست که من متوجه آن نشده‌ام گوشزد کنید. بعلاوه اگر حلش کنید که بسیار عالی می‌شود (;
خب چون تغییری نشد، من پاسخی که اگر خودم سر جلسه باشم می‌نویسم را در زیر گذاشتم. امیدوارم الهام‌بخش باشد.
+1 امتیاز
توسط AmirHosein (19,718 امتیاز)

نکتهٔ پرسش، ساخت یک افراز است!

یک مجموعه را بوسیلهٔ یک تعداد زیرمجموعه‌اش افراز کرده‌ایم هر گاه اجتماع این زیرمجموعه‌ها خود مجموعهٔ اصلی شود (پس هیچ عنصری از مجموعهٔ اصلی نیست که در این بخش‌بندی از قلم افتاده‌باشد)، هیچ دو زیرمجموعه‌ای اشتراک ناتهی نداشته‌باشند (پس هر عنصری از مجموعهٔ اصلی دقیقا در یک بخش است! به سخن دیگر، هیچ عنصری دو بار شمرده نشده‌است!) و در پایان هیچ یک از این زیرمجموعه‌ها تهی نباشد (برای جلوگیری از افزودن تعداد بی‌معنی زیرمجموعهٔ تهی به بخش‌بندی‌مان).

روشن است که اگر مجموعهٔ $A$ بوسیلهٔ زیرمجموعه‌های $A_1$ تا $A_n$اش افراز شده‌باشد داریم $|A|=|A_1|+\cdots+|A_n|$ (البته شرط متناهی بودن تعداد زیرمجموعه‌ها را برای افراز نداریم بنابراین می‌شود افراز نامتناهی نیز داشته‌باشیم البته مشروط بر نامتناهی بودن عدد اصلی مجموعهٔ اصلی). توجه کنید که $|A|$ یعنی عدد اصلی (که در حالت متناهی بودن، همان تعداد عنصر می‌شود) مجموعهٔ $A$.

زمان را به بازه‌های ۱۰۰ روزه تقسیم کنید، که حالا در پاسخ‌ کتاب‌ها از واژه و لفظ سال استفاده کرده‌اند، ما نیز از همان واژهٔ سال برای راحتی شما استفاده می‌کنیم.

مجموعهٔ $A$ را مجموعهٔ کل مریخی‌های وجود داشته از شروع زمان تا کنون بگیرید. چون هر مریخی دقیقا ۱۰۰ روز زنده‌است پس مریخی‌ای وجود ندارد که یک روز با عدد مشابه از دو سال را دیده‌باشد! یعنی اگر روز پنجم سال $x$ زنده‌بوده‌است، می‌توان مطمئن شد که روز پنجم سال $x-1$ و یا سال $x+1$ و یا روز پنجم از هر سالی به غیر از همان سال $x$ را نبوده‌است. سپاس از وجود فرض دقیقا نیمه‌شب (شروع یک روز از دید تقویم) به دنیا می‌آیند و دقیقا ۱۰۰ روز کامل زندگی می‌کنند، بحث اینکه نصف روز و ربع روز و حالت‌بندی وجود نخواهد داشت و می‌توانیم این‌گونه با قاطعیت بگوییم تنها در پنجم یک سال وجود داشته‌است. بعلاوه چون ۱۰۰ روز زنده‌هستند پس از هر نوع روزی دقیقا یکی دیده‌اند. اگر روز ششم به دنیا بیاید از ۶ تا ۱۰۰ سال تولدش و از ۱ تا ۵ سال پسین را وجود داشته‌است.

برای هر عدد $k$ از یک تا سال کنونی، یک زیرمجموعه از مجموعهٔ $A$ به نام $A_k$ به این شکل تعریف کنید. $A_k$ مجموعهٔ مریخی‌هایی باشد که در روز یکم سال $k$ زنده‌هستند. با توجه به اینکه هر مریخی‌ای از هر روز تقویم یک بار تجربه کرده‌است پس هر مریخی‌ای در یکی از این $A_k$ها قرار می‌گیرد. چون هیچ مریخی‌ای دو تا سال متفاوت از یک روز تقویم را تجربه نمی‌کند پس هیچ مریخی‌ای در اشتراک دو تا $A_k$ قرار نمی‌گیرد. تنها شرط باقیمانده برای افراز شدن، ناتهی بودن است. توجه کنید که به عنوان ریاضی‌دان باید دقیق باشید و از پیش خودتان به فرض‌های پرسش چیزی نیافزائید. چون اثباتتان نیاز دارد بگوئید برقرار است یعنی اشتباه! بلکه چیزی که اینجا باید گفت این است که یک سری $A_k$ها ممکن است تهی باشند، چون با توجه به دیدگاهی که برای پرسش گذاشتم تنها چیزی که می‌دانیم این است که مقدار تابع تجمعی تولدها در هر جایی از زمان که نگاه کنید فرد است که نتیجه می‌دهد زاد و ولد در هر روزی از زمان به غیر از روز یکم زمان، عددی زوج است و صفر نیز عددی زوج است پس نمی‌توان استناد داد که زاد و ولد در هر روز صورت می‌گیرد! پس یک سری $A_k$ها ممکن است خالی باشند، آنها را دور بریزید و مجموعه‌های باقیمانده را در نظر بگیرید. حاصل یک افراز برای $A$ است. پس عدد اصلی $A$ برابر جمع عدد اصلی تک تک زیرمجموعه‌های داخل این افراز می‌شود. چون اعضای $A$ کل مریخی‌های از اول زمان تا کنون هستند پس برابر با مقدار همان تابع تجمعی تولد مریخی ها می‌شود و نیاز نیست با مرگ و میر اثرش دهیم. این عدد، عددی فرد است. حالا برویم سراغ زیرمجموعه‌های داخل افراز. اگر همهٔ آنها عدد اصلی زوج داشته‌باشند آنگاه به تناقض می‌خوریم چون جمع یک تعداد عدد زوج، عددی زوج می‌شود. پس دست‌کم یک $k$ای وجود دارد که عدد اصلی $A_k$ فرد است. اما $A_k$ یعنی تداد مریخی‌های زنده در روز یکم سال $k$ام. پس یک روز از محور زمان یعنی روز یکم سال $k$ام یافت شد که تعداد فرد، مریخی در آن روز زنده هستند. توجه کنید که روز یکم را اختیاری برداشتیم و به جای روز یکم می‌توانستیم روز دوم تا روز صدم را برداریم پس با اثباتی مشابه ۹۹ زمان دیگر از محور زمان داریم که تعداد مریخی‌های زنده در آن روزها فرد است. هیچ یک از این ۱۰۰ زمانی که با این روش پیدا می‌کنیم تکراری نیستند چون درست است که برخی از آنها شانس یکسان بودن سالشان وجود دارد ولی روز تقویمشان فرق دارد مثلا یکم سال ۲۳ و دوم سال ۲۳! البته توجه کنید که $k$های مربوط به هر دفعه که این مسیر را می‌رویم می‌تواند متفاوت باشد. یعنی اگر برای روز یکم سال ۲۳ درآمد، الزامی ندارد که برای روز سوم نیز سال ۲۳ دربیاید.

این چرخ فلک که ما در او حیرانیم<br> فانوس خیال از او مثالی دانیم<br> خورشید چراغ دان و عالم فانوس<br> ما چون صوریم کاندرو حیرانیم
...