محمد در اصفهان زندگی می‌کند و حسین در تهران. بین اصفهان و تهران یک خط ارتباطی ارزان وجود دارد که محمد برای فرستادن پیغام‌هایش به حسین از آن استفاده می‌کند. هر پیغام دنباله‌ای از ارقام ۰ یا ۱ (تعدادی بیت) است. متاسفانه تعدادی از دشمنان این دو دوست قصد دارند بین‌شان تفرقه ایجاد کنند؛ به همین دلیل برخی مواقع تعدادی از بیت‌های پیغامی که از این خط مبادله می‌شود را تغییر می‌دهند. محمد که از این موضوع مطلع شد یک خط ارتباطی گران‌قیمت بین اصفهان و تهران خرید. این خط از جاهای مخفی می‌گذرد و تضمین شده که بیت‌هایی که از آن رد می‌شود تغییری نخواهد کرد. ولی چون این خط ارتباطی گران‌قیمت است محمد دوست دارد تا حد ممکن مقدار کمی اطلاعات را از طریق این خط منتقل کند.

فرض کنید محمد قصد دارد $۲^k$ بیت را از خط ارزان‌قیمت منتقل کند. برحسب اطلاعات قبلی او می‌داند حداکثر ۲ بیت از این اطلاعات ممکن است توسط دشمنان تغییر کند. حال او قصد دارد حداقل تعداد بیت را به عنوان اطلاعات کمکی هم‌زمان از خط گران‌قیمت برای حسین بفرستد به طوری که حسین با استفاده از این اطلاعات اضافی بتواند تشخیص دهد که آیا هیچ‌یک از $۲^k$ بیت دریافتی تغییر کرده است یا خیر.

ثابت کنید که اگر محمد کم‌تر از $k+۱$ بیت اطلاعات از خط گران‌قیمت بفرستد حسین نمی‌تواند قاطعانه تشخیص دهد که آیا بیت‌های فرستاده شده تغییر کرده‌اند یا خیر.

• سوال بعد
• سوال قبل