فرض کنیم 8 تا کلید داریم، A1 تا A8. و 8 تا هم لامپ، B1 تا B8 که هر Bi متناظر Ai هست. الان برداشتی که من از روش شما کردم اینه که پس از LogN بار نصف کردن، میتونید متوجه بشید که مثلاً کلید A1 متناظر با لامپ B1 و کلید A2 متناظر با لامپ B2 هست (اگر به صورت درخت دودویی در نظر بگیرید که هر بار فرزند سمت چپ رو برای ادامه‌ی الگوریتم انتخاب میکنید) و این رو برای سایر جفت‌ها هم باید انجام بدید و الگوریتمتون میشه (O(N*logN. یعنی من اینطوری متوجه شدم که در بار اول A1 تا A4 رو تست میکنیم و متوجه میشیم که B1 تا B4 متناظر با این‌ها هستند، بعد A1 تا A2 رو تست میکنیم و متوجه میشیم که B1 تا B2 متناظر با این دو هست، بعد A1 رو تست میکنیم و میبینیم B1 روشن شد پس B2 هم متناظر با A2 هست.
اگر اشتباه برداشت کردم، لطفاً برای همین N = 8 بگید که چطوری روشتون با logN (یا k*logN) بار میتونه مسأله رو حل کنه (هر بار چه کلیدهایی رو تست میکنید). طوری توضیح بدید که انگار به یکی که تا پنجم سواد داره دارین توضیح میدین
سؤال گسسته، توو یکی از تاپیکا یه سؤالی دیده بودم که دیدم در اصل چیزی که من اینجا نوشتم رو میخواد. اگه برای تعدادی عدد متوالی، تعداد عوامل 2 رو بنویسید یه حدسایی میتونید بزنید و زیاد پیچیده نیست. ریاضی 1 و 2 برای احل این مسائل کافیه و فقط اون مسأله‌ی احتمال هم یه قسمت نیاز به محاسبه‌ی یه کسر هست که نرم‌افزار هم قبوله.
اگر A پیشامد این باشه که هیچ نامه‌ای در پاکت خودش قرار نگیره، 'A میشه پیشامد اینکه حداقل یک نامه در پاکت خودش قرار بگیره، نه اینکه همه‌ی نامه‌ها در پاکت خودشون قرار بگیرند.
ضمناً از توضیحات صفحات قبل فکر کنم متوجه شده باشید که نامه‌ها و پاکت‌ها از هم متمایز هستند. در واقع برای N = 3 اینطوری میشه: 3 تا نامه داریم، A و B و C. سه تا هم پاکتشون که 'A و 'B و 'C. فضای حالت میشه !3 (مخرج کسر) که بدیهیه برای همه. اما صورت کسر میشه 2 چون برای این 3 نامه، 2 حالت هست که هیچ کدوم توو پاکت خودشون قرار نگیرند:
کد:
A -> B'
B -> C'
C -> A'
و
A -> C'
B -> A'
C -> B'
