یک مجتمع تفریحی 90 اتاق و100 عضو دارد. می خواهیم کلید های اتاقهای را به اعضای دهیم به طوری که هر 90 عضو که به مجتمع آمدند بتوانند وارد اتاقها شوند و هر عضو باید وارد اتاقی شود که کلید آن را در اختیار دارد و در ضمن دو نفر نمی توانند وارد یک اتاق شوند (اعضا نمی توانند کلید های خود را مبادله کنند). ثابت کنید برای رسیدن به این منظور حداقل 990 کلید لازم است و در ضمن 990 کلید کافی نیز هست.
اثبات حداقل بودنش:
کلید هر اتاق باید در دست حداقل 11 نفر باشدچون اگر در دست 10 نفر باشد در یکی از این انتخاب ها این ده نفر انتخاب نمی شوند پ 90 نفر دیگر که هیچ کدام کلید این اتاق را ندارن باید در 89 اتاق باقیمانده بروند که حداقل در یکی بیش از یک نفر می رود.
پس کلید هر اتاق باید حداقل دست 11 نفر باشد بنابر این حداقل به 990 کلید نیاز داریم!
اثبات کافی بودنش:
به 90 نفر اول کلید اتاقهای 1 تا 90 را می دهیم(به هر نفر کلید اتاق هم شماره ی خودش یعنی مجموعا 90 کلید به این افراد می دهیم.
به ده نفر باقیمانده کلید همه ی اتاقها را می دهیم یعنی مجموعا 900 کلید
که روی هم می شود 990 .
در این حالت هر گردایه ای از افراد شرط مسئله رو داره.
.
درسته؟
کلید هر اتاق باید در دست حداقل 11 نفر باشدچون اگر در دست 10 نفر باشد در یکی از این انتخاب ها این ده نفر انتخاب نمی شوند پ 90 نفر دیگر که هیچ کدام کلید این اتاق را ندارن باید در 89 اتاق باقیمانده بروند که حداقل در یکی بیش از یک نفر می رود.
پس کلید هر اتاق باید حداقل دست 11 نفر باشد بنابر این حداقل به 990 کلید نیاز داریم!
اثبات کافی بودنش:
به 90 نفر اول کلید اتاقهای 1 تا 90 را می دهیم(به هر نفر کلید اتاق هم شماره ی خودش یعنی مجموعا 90 کلید به این افراد می دهیم.
به ده نفر باقیمانده کلید همه ی اتاقها را می دهیم یعنی مجموعا 900 کلید
که روی هم می شود 990 .
در این حالت هر گردایه ای از افراد شرط مسئله رو داره.
.
درسته؟