چطور با ۱۰ نفر، یک بطری آلوده را از بین ۱۰۰۰ بطری پیدا کنیم؟

فرض کنید حتی مقدار بسیار کمی از نوشیدنی آلوده باعث میشود فرد آزمایشکننده دقیقاً ۲۴ ساعت بعد بیمار شود. همچنین فقط یک فرصت برای آزمایش دارید و تمام آزمایشها باید همزمان انجام شوند.
شاید اولین راهحل این باشد که برای هر بطری یک نفر در نظر بگیریم؛ اما اگر بدانیم هر نفر میتواند در آزمایش چند بطری مشارکت داشته باشد، مسئله شکل کاملاً متفاوتی پیدا میکند.
اینجاست که یکی از مفاهیم بنیادی علوم کامپیوتر، یعنی سیستم دودویی (Binary)، وارد ماجرا میشود.
یک مثال ساده با ۴ بطری و ۲ آزمایشکننده
برای درک بهتر ایده، ابتدا مسئله را با ۴ بطری و ۲ آزمایشکننده به نامهای آنا و بن بررسی کنیم.
- بطری اول: هیچکدام آزمایش نمیکنند.
- بطری دوم: فقط آنا آزمایش میکند.
- بطری سوم: فقط بن آزمایش میکند.
- بطری چهارم: هر دو آزمایش میکنند.
بعد از گذشت ۲۴ ساعت، چهار حالت متفاوت ممکن است اتفاق بیفتد:
| وضعیت آنا | وضعیت بن | بطری آلوده |
|---|---|---|
| سالم | سالم | بطری اول |
| بیمار | سالم | بطری دوم |
| سالم | بیمار | بطری سوم |
| بیمار | بیمار | بطری چهارم |
نکته مهم این است که هر حالت، یک الگوی منحصربهفرد دارد. بنابراین با بررسی وضعیت دو نفر، میتوانیم دقیقاً مشخص کنیم کدام بطری آلوده بوده است.
ارتباط این مسئله با سیستم دودویی
در سیستم دودویی، هر اطلاعات با استفاده از دو نماد صفر و یک نمایش داده میشود.
در مثال بالا، هر آزمایشکننده دقیقاً دو وضعیت دارد:
- سالم: صفر
- بیمار: یک
بنابراین وضعیت دو آزمایشکننده را میتوان با یک عدد دودویی دو بیتی نمایش داد:
| بطری | آنا | بن | کد دودویی |
|---|---|---|---|
| اول | سالم | سالم | 00 |
| دوم | بیمار | سالم | 10 |
| سوم | سالم | بیمار | 01 |
| چهارم | بیمار | بیمار | 11 |
هر بیت مشخص میکند که آیا فرد مربوط به آن بیت باید از بطری موردنظر نمونه دریافت کند یا نه.
با دو بیت، چهار حالت متفاوت داریم. با سه بیت، هشت حالت و با چهار بیت، شانزده حالت.
بهطور کلی، اگر تعداد آزمایشکنندگان را با n نشان دهیم:
حالا به سراغ ۱۰۰۰ بطری برویم!
اگر ۱۰ نفر در اختیار داشته باشیم، تعداد حالتهای ممکن برابر خواهد بود با:
یعنی ۱۰ نفر میتوانند ۱۰۲۴ حالت متفاوت را از یکدیگر تشخیص دهند؛ درحالیکه ما فقط ۱۰۰۰ بطری داریم.
برای این کار، به هر بطری یک کد دودویی ۱۰ بیتی اختصاص میدهیم. سپس هر نفر مسئول بررسی یکی از بیتهای این کد خواهد بود.
به این ترتیب، هر نفر از تمام بطریهایی که بیت مربوط به او در کدشان برابر یک است، نمونه دریافت میکند.
پس از انجام همزمان آزمایشها، وضعیت سالم یا بیمار بودن هر فرد مشخص میشود. با کنار هم قرار دادن این وضعیتها، یک کد دودویی به دست میآید که مستقیماً بطری آلوده را مشخص میکند.
برای مثال، اگر وضعیت افراد به شکل زیر باشد:
این عدد دودویی، شناسه بطری آلوده را مشخص میکند.
البته باید توجه داشت که این روش برای شناسایی یک بطری آلوده طراحی شده است و فرض میکند نتیجه آزمایش هر فرد دقیق و قابل اعتماد باشد.
یک میلیون بطری با فقط ۲۰ نفر!
حالا تصور کنید بهجای ۱۰۰۰ بطری، بیش از یک میلیون بطری داشته باشیم.
با ۲۰ آزمایشکننده، تعداد حالتهای قابل تشخیص برابر است با:
یعنی با استفاده از همین منطق، میتوان یک بطری آلوده را از میان بیش از یک میلیون بطری شناسایی کرد.
این مثال نشان میدهد که گاهی برای حل یک مسئله، افزایش تعداد افراد یا منابع ضروری نیست؛ بلکه کافی است روش استفاده از اطلاعات را تغییر دهیم.
جمعبندی: قدرت کدگذاری اطلاعات
مسئله شناسایی بطری آلوده، نمونهای جذاب از کاربرد سیستم دودویی و نظریه اطلاعات است.
در نگاه اول، برای بررسی ۱۰۰۰ بطری به ۱۰۰۰ آزمایشکننده نیاز داریم؛ اما با استفاده از کدگذاری مناسب، میتوانیم اطلاعات مربوط به تمام بطریها را در قالب ۱۰ بیت نمایش دهیم.
در واقع، هر آزمایشکننده یک بیت از اطلاعات را در اختیار ما قرار میدهد و ترکیب نتایج آزمایشها، پاسخ نهایی را مشخص میکند.
این ایده در علوم کامپیوتر، مخابرات، طراحی الگوریتمها و بسیاری از روشهای شناسایی و کدگذاری اطلاعات کاربرد دارد.