یک سفینه‌ی فضایی می‌خواهد پیام‌هایی را به زمین ارسال کند. دستگاه فرستنده‌ی این سفینه قادر است در هر مرحله یک «کلمه» به زمین بفرستد. هر کلمه یک دنباله به طول $n$ از صفر و یک است. بنابراین با استفاده از این فرستنده می‌توان هر پیغام را به‌صورت دنباله‌ای از کلمه‌ها به زمین ارسال کرد. به دلیل طولانی بودن مسیری که پیام باید طی کند تا به زمین برسد، در بین راه ممکن است در هر کلمه حداکثر یکی از صفرها تبدیل به یک و یا حداکثر یکی از یک‌ها تبدیل به صفر شود. هدف ما در این مسأله این است که برای فرستادن پیام‌ها تنها از بعضی کلمات خاص استفاده کنیم، به‌طوری‌ که پس از رسیدن پیام به زمین خطاها قابل تشخیص و رفع کردن باشند. برای مثال اگر $n=6 $ باشد، می‌توانیم از ۴ کلمه‌ی 000000، 111000، 000111، و 111111 استفاده کنیم. در این صورت اگر برای مثال کلمه‌ی 110111 به زمین برسد، می‌توانیم تشخیص دهیم که کلمه‌ی درست 111111، و نه کلمه‌ای دیگر از کلمات فوق، بوده است که در اثر خطا به 110111 تبدیل شده است.

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

۲) ثابت کنید که اگر $n=20 $باشد، برای این‌ که خطاها قابل تشخیص و رفع باشند، نمی‌توانیم بیش‌تر از ۵۰۰۰۰ کلمه در دستگاه داشته باشیم.

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