نقد، بررسی، پاسخ و رفع اشکال مرحله دوم نوزدهمین المپیاد کامپیوتر (فقط در اینجا)
- وضعیت
- ارسال ها
- 26
- لایک ها
- 0
- امتیاز
- 0
جوابا رو تو طلايي هاي دوره 26 زدن!
سلام.
جوابهای من اینهاست:
سوال 1: پنج مرحله
من اثبات کردم هیچ خانه ای در دقیقا 8 مربع حضور ندارد، پس با انتخاب خانه ی اول (هر انتخابی باشد)حداقل در بین 9 مربع 3در 3 شک داریم، بادومی در 5 باسومی در 3 با چهارمی در 2 ، پس بهپنجمین حرکت نیاز می شود.
سوال 2:a=0 و b=(101010101010101010...101010)2 البته b در مبنای 2 است و از 200 رقم تشکیل شده، 100تا صفر و 100 تا یک، به سادگی اثبات می شه که حداقل 100 جهش لازم داره.( باز هم وقت تایپ کردن اثبات رو ندارم)
یه چیزی به نام دسته یک تعریف کردم
دسته یک: تعدادی 1 در یک رشته ی n بیتی که بین آنها هیچ صفری نیست و هیچ دسته یک دیگری شامل آن نیست.
سپس اثبات کردم، با هر حرکت حدکثر یکی به تعداد دسته 1 ها اضافه می شود. پس 100 مرحله می خواد.
سوال 3: نمی توانند روی 4 راس یک مربع بزرگتر قرار بگیرند.
اثبات می شود اگر بتوانند روی 4 راس یک مرب بزرگتر قرار بگیرند، می توانند روی 4 راس یک مربع کوچکتر هم قرار گیرند( با انجام عکس همان حرکات)
حال اگر مربع اول را درون یک صفحه مختصات به واحد ضلع مربع قرار دهیم، اثبات می شود اگر ملخ ها ابتدای کار روی نقاط با مختصات صحیح باشند، همیشه روی نقاط با مختصات صحیح می مانند. پس هیچ گاه نمی توانند روی مربعی کوچکتر قرار گیرند، پس هیچ گاه نمی توانند روی مربع بزرگتر قرار گیرند.
سوال 4: من استقرا زدم ، ولی فکر نکنم نمره ی کامل رو بگیرم.
سوال پنجم:تعداد رنگ آمیزی های مجاز برای یک سطر(بدون در نظر گرفتن بقیه ستون ها) 144 است.( با رابطه ی بازگشتی و فیبوناچی می توانید 144 را به دست آورید.). پس ما چون 10 سطر داریم حداکثر 144 به توان 10 حالت داریم، که اثبات می شود از 10 به توان 25 کمتر است.
حال فرض کنید، جدول را به صورت شطرنجی رنگ کرده ایم، 50 خانه سیاه به دست می آید که هیچ کدام ضلع مشترک با دیگری ندارد، حال در رنگ آمیزی جدید تمام سفیدهای صفحه ی شطرنجی را سفید و هر کدام از این 50 تا را به 2 حالت سیاه یا سفید می کنیم، پس حداقل 2 به توان 50 حالت داریم که بیشتر از 10 به توان 15 است.(زیرا 2 به توان 50 برابر است با 1024 به توان 5 و بشتر است از 1000 به توان 5، پس بیشتر است از 10 به توان 15)(البته من این قسمت را که باید اثبات می کردیم بیش از 10 به توان 15 است را هم با رابطه بازگشتی رفتم، ولی بعد از امتحان فهمیدم این راه کوتاه تر است)
سوال ششم:به جای 20 حرکت، حکم را برای 10 حرکت اثبات می کنیم( برای 8 حرکت هم اثبات می شود).
فرض خلف می کنیم که در 10 حرکت متوالی به سراغ 10 سطل با بیش از 10 توپ رفته ایم، اثبات می شود که این سطل ها متمایز اند، همچنین سطل اول 10، سطل دوم 9 و... سطل نهم 2 و سطل دهم باید 1 توپ داشته باشد، پس در مجموع حداقل 55 توپ متمایز داشتیم، و تناقض ایجاد می شود.
سوال هفتم:استقرا روی تعداد کلید ها می زنیم، به ازای یک کلید که درست است،( چون همه به همان یک کلید وصل اند)فرض کنید به ازای n کلید درست باشد، به ازای n+1 اثبات می کنیم، یک کلید را مزنیم، تعدادی روشن میشود، بقیه که خاموش اند به این کلید وصل نیستند، پس حداقل به یکی از n کلید دیگر وصل اند، طبق فرض می توان با استفاده از آن n کلید، بیش از نیمی از بقیه را روشن کرد، از بین چراغ هایی که به وسیله کلید اول روشن کردیم، اگر کمتر مساوی نصف تا خاموش شود که مسئله حل است، و اگر نه دوباره کلید اول را می زنیم، مسئله حل می شود.
سوال هشتم: استقرا روی n می زنیم، برای 1 که درست است،اگربرای n-1درست باشد، برای n حکم را اثبات می کنیم، به این صورت که اگر بین کارتهای مرتضی دو تا اختلاف کمتر مساوی از d داشت، با dپرسش می فهمیم اختلاف یکی از این دوتا با کیان بیشتر مساوی دیگری است، پس n-1 کارت پیدا می شود که طبق فرض حل می شود، ولی اگر هیچ دوتایی اختلاف کمتر مساوی d نداشتند، حکم استقرا را قوی کرده و تبدیل به حکم زیر می کنیم، و مسئله حل خواهد شد:
اگر در بین n کارت اگر بدانیم یکی از آنها x<d-1 اختلاف با کیان دارد، می توانیم کارت دارای کمتر از d اختلاف را با کمتر از nd-x پرسش بیابیم.
جوابهای من اینهاست:
سوال 1: پنج مرحله
من اثبات کردم هیچ خانه ای در دقیقا 8 مربع حضور ندارد، پس با انتخاب خانه ی اول (هر انتخابی باشد)حداقل در بین 9 مربع 3در 3 شک داریم، بادومی در 5 باسومی در 3 با چهارمی در 2 ، پس بهپنجمین حرکت نیاز می شود.
سوال 2:a=0 و b=(101010101010101010...101010)2 البته b در مبنای 2 است و از 200 رقم تشکیل شده، 100تا صفر و 100 تا یک، به سادگی اثبات می شه که حداقل 100 جهش لازم داره.( باز هم وقت تایپ کردن اثبات رو ندارم)
یه چیزی به نام دسته یک تعریف کردم
دسته یک: تعدادی 1 در یک رشته ی n بیتی که بین آنها هیچ صفری نیست و هیچ دسته یک دیگری شامل آن نیست.
سپس اثبات کردم، با هر حرکت حدکثر یکی به تعداد دسته 1 ها اضافه می شود. پس 100 مرحله می خواد.
سوال 3: نمی توانند روی 4 راس یک مربع بزرگتر قرار بگیرند.
اثبات می شود اگر بتوانند روی 4 راس یک مرب بزرگتر قرار بگیرند، می توانند روی 4 راس یک مربع کوچکتر هم قرار گیرند( با انجام عکس همان حرکات)
حال اگر مربع اول را درون یک صفحه مختصات به واحد ضلع مربع قرار دهیم، اثبات می شود اگر ملخ ها ابتدای کار روی نقاط با مختصات صحیح باشند، همیشه روی نقاط با مختصات صحیح می مانند. پس هیچ گاه نمی توانند روی مربعی کوچکتر قرار گیرند، پس هیچ گاه نمی توانند روی مربع بزرگتر قرار گیرند.
سوال 4: من استقرا زدم ، ولی فکر نکنم نمره ی کامل رو بگیرم.
سوال پنجم:تعداد رنگ آمیزی های مجاز برای یک سطر(بدون در نظر گرفتن بقیه ستون ها) 144 است.( با رابطه ی بازگشتی و فیبوناچی می توانید 144 را به دست آورید.). پس ما چون 10 سطر داریم حداکثر 144 به توان 10 حالت داریم، که اثبات می شود از 10 به توان 25 کمتر است.
حال فرض کنید، جدول را به صورت شطرنجی رنگ کرده ایم، 50 خانه سیاه به دست می آید که هیچ کدام ضلع مشترک با دیگری ندارد، حال در رنگ آمیزی جدید تمام سفیدهای صفحه ی شطرنجی را سفید و هر کدام از این 50 تا را به 2 حالت سیاه یا سفید می کنیم، پس حداقل 2 به توان 50 حالت داریم که بیشتر از 10 به توان 15 است.(زیرا 2 به توان 50 برابر است با 1024 به توان 5 و بشتر است از 1000 به توان 5، پس بیشتر است از 10 به توان 15)(البته من این قسمت را که باید اثبات می کردیم بیش از 10 به توان 15 است را هم با رابطه بازگشتی رفتم، ولی بعد از امتحان فهمیدم این راه کوتاه تر است)
سوال ششم:به جای 20 حرکت، حکم را برای 10 حرکت اثبات می کنیم( برای 8 حرکت هم اثبات می شود).
فرض خلف می کنیم که در 10 حرکت متوالی به سراغ 10 سطل با بیش از 10 توپ رفته ایم، اثبات می شود که این سطل ها متمایز اند، همچنین سطل اول 10، سطل دوم 9 و... سطل نهم 2 و سطل دهم باید 1 توپ داشته باشد، پس در مجموع حداقل 55 توپ متمایز داشتیم، و تناقض ایجاد می شود.
سوال هفتم:استقرا روی تعداد کلید ها می زنیم، به ازای یک کلید که درست است،( چون همه به همان یک کلید وصل اند)فرض کنید به ازای n کلید درست باشد، به ازای n+1 اثبات می کنیم، یک کلید را مزنیم، تعدادی روشن میشود، بقیه که خاموش اند به این کلید وصل نیستند، پس حداقل به یکی از n کلید دیگر وصل اند، طبق فرض می توان با استفاده از آن n کلید، بیش از نیمی از بقیه را روشن کرد، از بین چراغ هایی که به وسیله کلید اول روشن کردیم، اگر کمتر مساوی نصف تا خاموش شود که مسئله حل است، و اگر نه دوباره کلید اول را می زنیم، مسئله حل می شود.
سوال هشتم: استقرا روی n می زنیم، برای 1 که درست است،اگربرای n-1درست باشد، برای n حکم را اثبات می کنیم، به این صورت که اگر بین کارتهای مرتضی دو تا اختلاف کمتر مساوی از d داشت، با dپرسش می فهمیم اختلاف یکی از این دوتا با کیان بیشتر مساوی دیگری است، پس n-1 کارت پیدا می شود که طبق فرض حل می شود، ولی اگر هیچ دوتایی اختلاف کمتر مساوی d نداشتند، حکم استقرا را قوی کرده و تبدیل به حکم زیر می کنیم، و مسئله حل خواهد شد:
اگر در بین n کارت اگر بدانیم یکی از آنها x<d-1 اختلاف با کیان دارد، می توانیم کارت دارای کمتر از d اختلاف را با کمتر از nd-x پرسش بیابیم.
سلام.
آقای سعادت فر، به نظر من سوال شش اصلا مشکل نداره، چون گفته :"...اگرk توپ درون آن بود آنها را خارج کرده و ..." این یعنی اینکه پس از انتخاب سطل، سطل خالی می شه، (همون طور که دیدید اگه فرض نکنیم که سطل خالی می شه، دیگه نمی شه حکم را اثبات کرد)
آقای bi-gham جواب من برای سوال 7 اصلا مشکل نداره، منم در جواب فرض کردم با زدن 1 کلید وضعیت تعدادی از لامپها عوض می شود ولی به مشکل نخوردم، چون وقتی اولین کلید را می زنم، تعدادی چراغ روشن می شود، بقیه چراغها به این کلید وصل نیستند، پس به بقیه کلیدها وصل اند و طبق فرض می شه بیشتر از نصف آنها را روشن کرد، اگر بعد از روشن کردن بیش از نصف آن چراغها، بیش از نصف چراغهایی که به کلید اول وصل بود، خاموش شد، کلید اول را دوباره می زنیم، با این کار در بقیه تغییر ایجاد نشده ولی بیش از نیمی از چراغهای اولی روشن می شود.
آقای سعادت فر، به نظر من سوال شش اصلا مشکل نداره، چون گفته :"...اگرk توپ درون آن بود آنها را خارج کرده و ..." این یعنی اینکه پس از انتخاب سطل، سطل خالی می شه، (همون طور که دیدید اگه فرض نکنیم که سطل خالی می شه، دیگه نمی شه حکم را اثبات کرد)
آقای bi-gham جواب من برای سوال 7 اصلا مشکل نداره، منم در جواب فرض کردم با زدن 1 کلید وضعیت تعدادی از لامپها عوض می شود ولی به مشکل نخوردم، چون وقتی اولین کلید را می زنم، تعدادی چراغ روشن می شود، بقیه چراغها به این کلید وصل نیستند، پس به بقیه کلیدها وصل اند و طبق فرض می شه بیشتر از نصف آنها را روشن کرد، اگر بعد از روشن کردن بیش از نصف آن چراغها، بیش از نصف چراغهایی که به کلید اول وصل بود، خاموش شد، کلید اول را دوباره می زنیم، با این کار در بقیه تغییر ایجاد نشده ولی بیش از نیمی از چراغهای اولی روشن می شود.
سلام آقای bi gham
اگه یه کم روی جوابم فکر کنید خودتون متوجه می شید که جواب بدون ذکر آن جمله کاملا درست است و ما داریم سوال را برای تمام وضعیتها اثبات می کنیم و دیگر نیاز به گفتن آن در فرض نیست.
راستی به اونهایی که قبول شدند تبریک می گم، مخصوصا اصفهانیها( به نژاد، جلالی، شاملی، درخشان و خودم(محمد زابلیان)).
از اعضای این سایت کیا دیگه قبول شدند که پیشاپیش با هم رفیق بشیم؟
اگه یه کم روی جوابم فکر کنید خودتون متوجه می شید که جواب بدون ذکر آن جمله کاملا درست است و ما داریم سوال را برای تمام وضعیتها اثبات می کنیم و دیگر نیاز به گفتن آن در فرض نیست.
راستی به اونهایی که قبول شدند تبریک می گم، مخصوصا اصفهانیها( به نژاد، جلالی، شاملی، درخشان و خودم(محمد زابلیان)).
از اعضای این سایت کیا دیگه قبول شدند که پیشاپیش با هم رفیق بشیم؟
SHIRY گفت
pluto-sampadi گفت
چرا هيچكي نمياد اينجا؟يعني كامپيوتري نداريم؟!! 
سلام.
......................................
دانش اموزانیک کلاس 30 نفره در یک ازمون شرکت کردند.در این ازمون بالاترین نمره 20و پایین ترین نمره 5 بوده است در ضمن میدانیم نمرات 12و نمره ی نفر 10ام کلاس 15 بوده است دراین کلاس. حداکثر چند نفر نمره ی کمتر از 10 گرفته اند
- وضعیت