پرش به محتویات

صفحه ۷

سوال شب سیزدهم

 سلامی دوباره

فرض کنید دور یک میز گرد ‎50‎ دختر و ‎50‎ پسر نشسته اند . ثابت کنید یک دختر و پسر وجود دارند که بین انها دقیقا یک دختر و یک پسر نشسته باشد 

ارشیا سلطانی

شب خوش :)

طلاهای دوره ۲۸ ۱۳۹۷/۱۱/۰۸ · ۲۲:۲۳

سوال شب دوازدهم

سلاااااااااااام:))

خوبین؟

خب مثل قبل. جواب سوال قبلی رو تو دیسکورد میگیم!

و حالا سوال امشب!

درخت T با n راس داریم. به جایگشت p میگیم خوب اگه به ازای هر یال درخت که بین u,v هستش، بین Pv,Pu هم یک یال باشه.

ثابت کنید توی هر جایگشت خوب یا x ای وجود داره که Px=x و یا x,y وجود دارن که Py=x,Px=y.

نویسنده: میکائیل

طلاهای دوره ۲۸ ۱۳۹۷/۱۱/۰۷ · ۲۳:۳۴

سوال شب یازدهم

سلام بچه ها. فکر می کردید ما خسته شدیم و دیگه قرار نیست سوال شب بذاریم؟!!!!!

آقا تیزی یه جمله داره میگه:‌ هه! آقا رو باش :)

ضمن یاداوری این نکته که جواب سوالات شب های قبل توی دیسکورد موجود هستش میریم سراغ سوال امشب:

یک عدد اول به نام p داریم.

ثابت کنید یال های گراف K p^2‌ (گراف کامل پی دو راسی) رو می تونیم به تعدادی K p (گراف کامل p راسی) افراز کنیم. دقت کنید که در افراز هر یال دقیقا یک بار می آید.

موفق باشید. خدانگهدار همتون.

امیرمحمد ایمانی

طلاهای دوره ۲۸ ۱۳۹۷/۱۱/۰۶ · ۲۲:۵۳

الگوریتم هفتگی-برنامه نویسی پویا

در راستای انقلابی که تو شااززز ایجاد شده قصد داریم به صورت هفتگی سوال منتشر کنیم. سوالاتی که میدیم به این صورته که از یه تگ خاصه و از آسون به سخت داره و سعی میکنیم برای همه مفید باشه و هرچقدم خفنید بتونید استفاده کنید از سوالات.
 
سوالا به ترتیب آسون به سخت سورت شدن!! تقریبن تضمین میشه که هر پستیو اگه تا آخرین سوال حل کنید کامل اون مبحث براتون بسته میشه!
 
 
 
تگ این هفته برنامه نویسی پویا یا همون dynamic programming(dp) هستش.
 
از اینجا به بعد سوالا سخت تر میشن.
 
 
مهدی جعفری

طلاهای دوره ۲۸ ۱۳۹۷/۱۱/۰۶ · ۰۸:۰۰

سوال شب دهم

سلام دوستان. ببخشید که سوالمون را با کمی تاخیر ارائه میدیم.

برای دسترسی به راه حل های سوالات شب های قبل ما را در پیام رسان دیسکورد دنبال کنید.

و حالا سوال امشب‌ یا بهتره بگم امروز:

گراف Q3 را در نظر بگیرید(برای آشنایی بیشتر با Qn می توانید به اینجا مراجعه کنید). خرسی به نام جیمز بر روی راس صفر این گراف قرار دارد. می دانیم در راس پنجم گراف مقدار زیادی عسل ذخیره شده است. به جیمز گفته شده است که اگر پس از ۲۰۱۸ ثانیه بر روی راس پنج قرار بگیری همه عسل ها مال تو می شود و در غیر این صورت هیچ عسلی به تو داده نمی شود. از ان جایی که جیمز یک خرس است دوست دارد همه عسل ها را به دست بیاورد ولی از آن جایی که سواد درست و حسابی ندارد تصمیم می گیرد که در هر ثانیه به صورت رندوم از یکی از یال های متصل به راس فعلیش عبور کرده و به راس دیگری می رود. حال جیمز می خواهد بداند که به چه احتمالی عسل ها را به دست خواهد آورد. به او کمک کنید تا این مقدار را حساب کند. دقت کنید که لزومی ندارد قبل از ۲۰۱۸ ثانیه به راس پنج نرسد.

پیشنهاد می شود که پس از حل سوال به ازای همه مکان های ابتدایی خرس پاسخ مسئله را به دست آورید.

با تشکر از همراهی شما دوستان. موفق و پیروز باشید. خداحافظ

امیرمحمد ایمانی

طلاهای دوره ۲۸ ۱۳۹۷/۱۰/۲۸ · ۲۴:۱۲

سوال شب نهم

سلام بچه ها. بازم ما اومدیم با یه سوال جدید :)

راستی قبل از سوال امشب خوبه که یاداوری کنم توی پیام رسان دیسکورد به ما بپیوندید. راه حل سوالات شب های قبل توی کانال شاز در پیام رسان موجود هستش. اگر هم راه حلی برای سوالات داشته باشید می تونید اونا رو توی کانال بیان کنید و  ما حتما بررسیشون می کنیم. پس حتما ما را توی پیام رسان دنبال کنید.

حالا میریم سراغ سوال امشب:

یه جدول ۲۰۱۸ * ۲۰۱۸ داریم که با دومینوهای ۲ * ۱ پرش کردیم(دومینوها می توانند عمودی و افقی باشند) به طوری که هر خانه توسط دقیقا یک دومینو پوشانده شده است. ثابت کنید تعداد دومینوهای افقی و عمودی با هم برابر نیست.

موفق باشید. خداحافظ :)

امیرمحمد ایمانی

طلاهای دوره ۲۸ ۱۳۹۷/۱۰/۲۶ · ۲۳:۱۲

سوال شب(عصر) هشتم

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

طلاهای دوره ۲۸ ۱۳۹۷/۱۰/۲۵ · ۱۶:۴۰

سوال شب هفتم

سلام سلام صد تا سلام.
باور کردنش سخته ولی یه هفته گذشته و ما هنوز داریم ادامه میدیم :)

خب اول می پردازیم به راه حل سوال دیشب. کسانی که می خوان سوال براشون نسوزه این قسمت را نخونن.

واضحه که تعداد تطابق های x تایی توی گراف G که برابر هستش با c(n, x) ^ 2 (انتخاب x از n به توان دو) ضرب در x فاکتوریل. حالا می خواهیم ثابت کنیم تعداد تطابق های x تایی گراف F هم همین قدره. فرض می کنیم جواب مسئله مون هستش (f(n, x. حالا می خواهیم یه رابطه بازگشتی برای f پیدا کنیم. با کمی تلاش به رابطه بازگشتی زیر می رسیم:

(f(n, x) = f(n - 1, x) + f(n - 1, x - 1) * (2n - x

برای اثبات رابطه بازگشتی بالا میاییم راس n ام را در نظر می گیریم. یا با هیچ کس تطابق داده نمیشه که در این صورت میشه (f(n - 1, x. یا به یه راس دیگه تطابق داده میشه. در این صورت میاییم اول به (f(n - 1, x - 1 طریق یه تطابق x - 1 تایی توی n - 1 نفر اول پیدا می کنیم. حالا چون n به همه 2n - 1 راس قسمت دیگه وصله و از بین اونا دقیقا x - 1 تاشون با راس دیگه تطابق داده شدن, راس n ام 2n - x انتخاب برای تطبیق داره. پس رابطه بازگشتی بالا ثابت میشه. حالا با استفاده از استقرا بر روی n و مقدار کمی جبر می توانید ثابت کنید که (f(n, x برابر است با c(n, x) ^ 2 (انتخاب x از n به توان دو) ضرب در x فاکتوریل. بنابر این مسئله ثابت می شود. 3:

حالا سوال امشب:

در مدرسه ای n دانش آموز وجود دارند. هر دانش آموز در تعدادی گروه عضو است. اگر دو گروه دو دانش آموز مشترک داشته باشند آنگاه تعداد اعضایشان متفاوت است. ثابت کنید تعداد گروه ها از (n-1)*(n-1) کمتر است. ( گروه یک نفره نداریم )

راستی بچه ها یه خبر دیگه ای هم براتون دارم. ما واسه راحت تر کردن ارتباط خودتون با خودمون و خودتون با خودتون تصمیم گرفتیم از یه اپ پیام رسانی به اسم discord استفاده کنیم. هم اینکه فیلتر نیست هم اینکه طبقه بندی خوبی داره و هم اینکه جذابه :))

از این به بعد سوالای شب و یه سری چیزای دیگه رو اونجا میذاریم. خلاصه که جمع بشید اینجا پرچم شازو ببریم بالا :*

بعد که اپو نصب کردین با این لینکه بیاید تو.

بای بای :)

حمیدرضا کلباسی

طلاهای دوره ۲۸ ۱۳۹۷/۱۰/۲۴ · ۱۲:۱۱

۱ ۶ ۷ ۸ ۳۸