Pigeonhole Principle

Pigeonhole Principle আসলে খুব সিম্পল একটা নিয়ম—কিন্তু অনেক শক্তিশালী।

🕊️ Pigeonhole Principle কী?

সহজ ভাষায়:

যদি n+1 টি বস্তু n টি ঘরে রাখো, তাহলে অন্তত একটি ঘরে কমপক্ষে ২টি বস্তু থাকবেই।

এই কথাটাই Pigeonhole Principle।

সহজ উদাহরণ (বাস্তব জীবন)

1️⃣ ৩টা পায়রা, ২টা খাঁচা

→ একটা খাঁচায় অন্তত ২টা পায়রা থাকবেই।

2️⃣ ১৩ জন মানুষ, ১২ মাস

→ অন্তত দুজনের জন্মমাস একই হবেই।

3️⃣ ৫টা কলম, ২টা পকেট

→ কোনো এক পকেটে কমপক্ষে ৩টা কলম পড়বেই।

গণিতের ভাষায়

যদি

• মোট বস্তু = N

• মোট ঘর = k

তাহলে অন্তত এক ঘরে থাকবে

টা বস্তু।

এখন আমাদের সমস্যায় এটা কীভাবে এলো?

আমরা বলেছিলাম:

একজন মানুষ A-এর সাথে ৫টা edge আছে

প্রতিটা edge হয় লাল নয় নীল

এখানে:

• বস্তু (pigeons) = ৫টা edge

• ঘর (holes) = ২টা রঙ (লাল, নীল)

তাহলে,

মানে:

অবশ্যই অন্তত ৩টা edge একই রঙের হবে

এইটুকুই আমরা দরকার ছিল প্রমাণের জন্য।

এক লাইনে মনে রাখার ট্রিক

“বস্তু বেশি, ঘর কম ⇒ কোথাও না কোথাও ভিড় হবেই”