جواب : $C(n,k-1)$

ساخت : به هر قفل یک مجموعه k - 1 عضوی از n نفر متناظر می کنیم. حالا به نفر x ام قفل با مجموعه S را می دهیم اگر و تنها اگر x عضو S نباشد. واضح است که اگر کمتر از k نفر بخواهند قفل ها را باز کنند حداقل قفلی که هیچ کدام از آنها در آن مجموعه نیستند را نمی توانند باز کنند چون هیچ یک از آن ها کلید آن قفل را ندارد. ( و قطعن این قفل وجود دارد. چرا؟ ) و هر k تایی می توانند همه قفل ها را باز کنند. چون هر قفلی را در نظر بگیریم دقیقا k - 1 نفر کلیدش را ندارند پس حداقل یک نفر از آن k نفر کلیدش را دارد.

اثبات این که کمتر نمیشه! : کمترین تعداد قفل را t در نظر می گیریم. و میدانیم که t کمتر از انتخاب k - 1 از n است. یک گراف دو بخشی درست می کنیم که یک طرف قفل ها هستند و طرف دیگر هر انتخاب k - 1 نفره از این n نفر. قفل ها را با G و مجموعه نفرات را با C نمایش می دهیم. بین Ci و Gj یال می گذاریم اگر و تنها اگر قفل Gj توسط مجموعه نفرات Ci باز شود.

خب. یک Ci را در نظر بگیرید. فرض کنید به Gj یال نداشته باشد. هر کسی به غیر از افرادی که در Ci هستند باید بتواند Gj را باز کند. ( چون هر k نفری می توانند قفل ها را باز کنند. ) پس هر C دیگری به غیر از Ci باید بتوانند Gj را باز کنند. ( چون شخصی در آنها هست که در Ci نیست. ) پس یعنی به ازای هر G دقیقا یک Ci است که نمی تواند آنرا باز کند. پس یعنی تعداد یال های گراف دقیقا $ t * C(n,k-1) - t$ تا است. ولی از طرفی هر Ci به حداقل یک قفل یال ندارد. پس تعداد یال های گراف حداکثر $ t * C(n,k-1) - C(n,k-1)$ است. که این کمتر از تعداد یال های گراف است. پس تناقض!

تمام! :دی