سوالی از فرانسه 2005 (ترکیبیات)
- ارسال ها
- 114
- لایک ها
- 3
- امتیاز
- 0
سلام آقای گوهرشادی خسته نباشید.
کمترین مقدار n برابر 8 هست
اینکه کمتر از 8 نمیشه رو اینطوری اثبات میکنیم. اولا اگه قرار باشه n کمتر از 8 باشه ، باید مخالف 3 و 4 و 5 باشه چون اگه یکی از اینا باشه میدونیم 3 نفر هستن که یه زبانو میدونن و 3 از نصف 5 بیشتره که با فرض دوم در تناقضه. اگه n برابر 6 یا 7 باشه ، هر زبان رو حداکثر 3 نفر بلدن (به خاطر شرط دوم) پس به ازای هر 3 تا از افراد باید حداقل یه زبون داشته باشیم که نتیجه میده تعداد زبونا حداقل
یا
باید باشه که از 14 بیشتره.
مثال واسه 8 : مثالو اینطوری میسازیم که 8 نفرو به دو دسته 4 نفر تقسیم میکنیم طوری که تو هر دسته همه یه زبونو بلد باشن مثلا 4 نفر اول زبون 1 و 4 نفر دوم زبون 2
حالا اگه هر دو نفر از گروه یک دو تا زبونو مشترکا بلد باشن و تو گروه تو 2 نفر یکی از اون دو زبون و 2 نفر دیگه اون یکی زبونو بلد باشن (فقط باید دو نفر گروه دو رو یه جور خاص تعیین کنیم که تو مثال مینویسم) شرط مسئله برقراره. اینطوری :
گروه یک
{1 , 3 , 6 , 9 , 10 , 13 , 14} نفر اول
{1 , 3 , 6 , 7 , 8 , 11 , 12} نفر دوم
{1 , 4 , 5 , 7 , 8 , 13 , 14}نفر سوم
{1 , 4 , 5 , 9 , 10 , 11 , 12}نفر چهارم
گروه دو
{2 , 3 , 5 , 9 , 8 , 13 , 12}نفر پنجم
{2 , 4 , 5 , 10 , 7 , 14 , 12}نفر ششم
{2 , 4 , 6 , 9 , 8 , 14 , 11}نفر هفتم
{2 , 3 , 6 , 10 , 7 , 13 , 11}نفر هشتم
کمترین مقدار n برابر 8 هست
اینکه کمتر از 8 نمیشه رو اینطوری اثبات میکنیم. اولا اگه قرار باشه n کمتر از 8 باشه ، باید مخالف 3 و 4 و 5 باشه چون اگه یکی از اینا باشه میدونیم 3 نفر هستن که یه زبانو میدونن و 3 از نصف 5 بیشتره که با فرض دوم در تناقضه. اگه n برابر 6 یا 7 باشه ، هر زبان رو حداکثر 3 نفر بلدن (به خاطر شرط دوم) پس به ازای هر 3 تا از افراد باید حداقل یه زبون داشته باشیم که نتیجه میده تعداد زبونا حداقل
مثال واسه 8 : مثالو اینطوری میسازیم که 8 نفرو به دو دسته 4 نفر تقسیم میکنیم طوری که تو هر دسته همه یه زبونو بلد باشن مثلا 4 نفر اول زبون 1 و 4 نفر دوم زبون 2
حالا اگه هر دو نفر از گروه یک دو تا زبونو مشترکا بلد باشن و تو گروه تو 2 نفر یکی از اون دو زبون و 2 نفر دیگه اون یکی زبونو بلد باشن (فقط باید دو نفر گروه دو رو یه جور خاص تعیین کنیم که تو مثال مینویسم) شرط مسئله برقراره. اینطوری :
گروه یک
{1 , 3 , 6 , 9 , 10 , 13 , 14} نفر اول
{1 , 3 , 6 , 7 , 8 , 11 , 12} نفر دوم
{1 , 4 , 5 , 7 , 8 , 13 , 14}نفر سوم
{1 , 4 , 5 , 9 , 10 , 11 , 12}نفر چهارم
گروه دو
{2 , 3 , 5 , 9 , 8 , 13 , 12}نفر پنجم
{2 , 4 , 5 , 10 , 7 , 14 , 12}نفر ششم
{2 , 4 , 6 , 9 , 8 , 14 , 11}نفر هفتم
{2 , 3 , 6 , 10 , 7 , 13 , 11}نفر هشتم
