موسیقی یا پیام جاسوسی
یک شبکه بزرگ جاسوسی از روش خاصی برای فرستادن پیام به ماموران و جاسوسان خود در فاصله های دور استفاده می کند؛ به این ترتیب که پیام های مورد نظر خود را به صورت دنباله هایی از ارقام صفر و یک رمزگذاری می کند و این دنباله ها را در قالب نت های موسیقی که صدای آن ها کم و زیاد می شود از طریق امواج معمولی رادیویی ارسال می کند. ماموران می دانند که کاهش طنین در موسیقی حاوی پیام به معنی صفر و افزایش آن نشانه ی یک است. در این جا حالت خاصی را در نظر می گیریم که در آن هر پیام یک دنباله ی چهارتایی از صفر و یک هاست (یک دنباله چهاربیتی).
این شبکه می خواهد برای 9 نفر از مامورانش پیام بفرستد، ولی از آنجا که زیاد شدن طول پیام احتمال شناسایی و کشف آن را زیاد می کند سعی می کند طول کل پیام ارسالی تا حد ممکن کوتاه باشد. به این دلیل، در صورت امکان پیام های مورد نظر خود را با هم ترکیب و یک جا ارسال می کند. مثلا هر گام بخواهد پیام 0110 را به یکی از ماموران و پیام 1011 را مامور دیگر بفرستد، می تواند آن ها را به صورت 011011 ترکیب و یک جا ارسال کند. البته در این حالت باید قبل از ارسال این پیام ترکیبی، به مامور اول اطلاع دهد که از رقم اول شروع به خواندن کند و به مامور دوم بگوید که از رقم سوم شروع به خواندن کند. برای اطلاع دادن محل شروع پیام هر مامور (شماره رقم آن) هم از نت موسیقی خاصی برای آن مامور استفاده می شود.
1- این شبکه می خواهد پیام های 0000 ، 0011 ، 0100 ، 0110 ، 0111 ، 1011 ، 1100 ، 1101 و 1110را به مامورانش بفرستد. متخصصی کد گذاری شبکه موفق به یافتن دنباله ای به طول 15 بیت برای ترکیب این 9 پیام شده اند. آیا شما می توانید دنباله ای به طول 14 یا کمتر بیابید که شامل همه این 9 پیام باشد؟
2- فرض کنید تعداد ماموران این شبکه از 9 نفر به 14 نفر افزایش پیدا کرده است. آیا می توانید دنباله ای 19 بیتی پیدا کنید که شامل هر مجموعه 14 تایی دلخواه از پیام های 4 بیتی باشد؟
3- آیا می توان یک دنباله 18 بیتی که 14 دنباله 4 بیتی مشخص که از قبل به شما داده شده اند، زیر دنباله های آن باشند؟ (به تفاوت این سوال و سوال قبل دقت کنید. در سوال قبل دنباله 19 بیتی باید شامل هر مجموعه دلخواه از مجموعه 4 بیتی باشد، ولی در این سوال 14 دنباله داده شده است که دنباله 18 بیتی باید شامل هر یک از آن ها باشد. نشان دهید که بدون توجه به این که 14 دنباله انتخاب شده، چه دنباله هایی هستند؛ می توانید دنباله 18 بیتی مورد نظر را تشکیل دهید.)
4- نشان دهید مجموعه هایی از 14 دنباله 4 بیتی وجود دارند که هیچ دنباله ای به طول 18 بیت یا کمتر شامل همه آن ها نیست.
منبع: معماهای الگوریتمی، دکتر قدسی و یاشار گنجعلی، انتشارات فاطمی
