سوالی دیگر از آمریکا 1982

[Goharshady]

در اجتماعی که از 1982 نفر تشکیل شده است ، در بین هر 4 نفر می توان 1 نفر را پیدا کرد که با 3 نفر دیگر آشنا باشد. حداقل تعداد کسانی که با همه ی دیگران آشنا هستند چقدر است؟

 

[abdi]

1979 نفر

براي اثبات فرض مي‌كنيم 1978 نفر هستند كه همه را مي‌شناسند. پس 4 نفر هستند كه همه را نمي‌شناسند. ثابت مي‌شود در اين صورت مي‌توان يك جمع 4 نفره جدا كرد كه هيچ كسي 3 نفر ديگر را نشناسد (شرمنده از اينكه اينقدر مختصره. حال نوشتن نداشتم

)

 

[Goharshady]

درسته
آفرین!

 

[mimilad]

پاسخ : سوالی دیگر از آمریکا 1982

برای اثبات میتوان به استقرا نیز حکم را اثببات کرد البته با توجه به این که به وضوح حداقل یه نفر است که همه را بشناسد.

 

[mandana_hashemi]

پاسخ : سوالی دیگر از آمریکا 1982

خیلی ضایع است که جواب جز 3نفر که همه رونشناسن نمی تونه باشه والا 4نفر میشه پیدا کرد که همو نشناسن
استقرا اینام دیگه نمیاد وسط
البته به نظر من

 

[حالا هرکی]

پاسخ : سوالی دیگر از آمریکا 1982

داد میزنه که من با منتل حل میشم

 

[ali math]

پاسخ : سوالی دیگر از آمریکا 1982

سلام دوست عزیز(حالا هرکی)
اگه میشه راه منتلش سوال را بنویسید

 

[hoco.hc]

پاسخ : سوالی دیگر از آمریکا 1982

منتل چیه؟:39:
خیلی جالبه بدونید که یه چیزی شبیه این سوال مرحله یک المپیاد ایران بوده
:91:
( پ ن : ali math و حالا هر کی ، بوگو بیبینم، منو می شناسی ؟ )

 

[tanaz19]

پاسخ : سوالی دیگر از آمریکا 1982

منتل چیه؟:39:
خیلی جالبه بدونید که یه چیزی شبیه این سوال مرحله یک المپیاد ایران بوده
:91:
آره اون کلاغ و آنتنا فک کنم

 

[goodarz]

پاسخ : سوالی دیگر از آمریکا 1982

قضیه منتل در واقع یه خالت خاصی از قضیه توران محسوب میشه: Turán's theorem - Wikipedia, the free encyclopedia

 

[hoco.hc]

پاسخ : سوالی دیگر از آمریکا 1982

بگو همون قضیه تورانه دیگه. منتل چیه آخه