سوال مجموعه ها: یافتن همه مقادیر $n$ وقتی$k$ ماکسیمم است
زیرمجموعه هایی با بیش از نصف عضو و زیرمجموعه ای که با همه عضو مشترک دارد
لطفا قضیه اسپرنر و کاربردش را توضیح دهید
میخواهیم اعداد مجموعه ی {1, 2, 3, ... n } را به 3 دسته تقسیم کنیم طوری که مجموع اعداد دسته ها با هم برابر باشند. مقدار لازم و کافی n چیست ؟ ( اگر و فقط اگر چی باشه )
سماق‌جان محدودیت 70 کاراکتر به 40 کاراکتر کاهش یافت. در هر صورت اگر در مورد سایت پیشنهادی داری اون رو توی وبلاگ بگو نه توی خود کاهو. ممنون
2014-07-26 02:10:43 -0600 کاهوآخه اگه اون پرانتز رو نمینوشتم از 70 کاراکتر کمتر میشد و قبول نمیکرد !
2014-07-26 07:05:21 -0600 سماق دوسلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com
2015-08-06 08:59:38 -0600 امیر شکریابتدا به عنوان لم ثابت می کنیم که اگر k درست باشد k+6 هم درست می باشد .
خب اعداد k+1,k+2,k+3,k+4,k+5,k+6 را اینطور دسته بندی می کنیم :(طوری که مجموع هر دسته عددی ثابت شود(k+7))
1)k+1,k+6
2)k+2,k+5
3)k+3,k+4
خب حال اگر k درست باشد یعنی بتوان به سه دسته تقسیم کرد به طوری که مجموع هر دسته عددی ثابت شود به هر کدام از دسته ها یکی از دسته های بالا را اضافه می کنیم خواهیم دید که هنوز حکم برقرار است.
برای n هایی که به پیمانه ی سه مساوی 1 می باشند چون مجموعشان به پیمانه ی 3 صفر نیست پس نمی توان به سه دسته تقسیم کرد .
حال برای برای n های 3k+2 , 3k کافیست n مساوی 5 6 8 9 ثابت کنیم انگاه طبق لم تمام اعداد 3k+2 , 3k ثابت می شود
برای 5 : دسته اول : 5 دسته ی دوم : 2 3 دسته ی سوم 1 4
برای 6 : دسته اول : 1 6 دسته ی دوم : 2 5 دسته ی سوم 3 4
برای 8 : دسته اول 8 4 دسته ذوم 7 5 دسته سوم 1 2 3 6
برای 9 : دسته اول 1 5 9 دسته دوم 2 6 7 دسته ی سوم 3 4 8
جواب کوتاه تر »
فرض میکنیم به ازای n ، مجموعه فوق به سه دسته A ، B ، C با مجموع دوبدو برابر افراز شود
حال مساله را برای n + 3 حل میکنیم.
فرض میکنیم دسته A شامل عضو {1} باشد .
سه عضو n + 1 ,n + 2 , n + 3 را که تازه افزوده شده اند را طبق الگوی زیر به سه دسته می افزاییم به طوری که مجموعشان همچنان دوبدو برابر باشد .
A - {1} + {n + 3} = A
B + {n + 1} + {1} = B
C + {n + 2} = C
( اینکه چرا برای n % 3 = 1 ممکن نیست و حالات پایه n= 5 و n = 6 رو نگفتم چون توی اثبات قبلی اومده ، این روش به نظر تمیز تر و قابل فهم تر از روش قبلیه که توسط طوفان ارائه شد )
n=3k يا n=3k+2 و n>4 اثباتش با استقراست و كاملا گلابي براي n=3k+1 هم جمع اعداش به سه بخش پذير نميشه !
طوفان راست میگه ! به عنوان اولین جوابتون وجهه ی خوبی نشون ندادید .
2014-07-23 06:34:22 -0600 سماق دو