یک جدول ۱×۷ خالی داریم که به خانههای آن از سمت چپ به راست، شمارههای ۰ تا ۶ را نسبت دادهایم. میخواهیم عناصر a٬ b تا g را به آن اضافه کنیم و برای هر کدام، یک مکان اولیه مطابق جدول روبهرو در نظر گرفتهایم.
عناصر مذکور به ترتیب دلخواه برای درج به جدول وارد میشوند. اگر مکان اولیهی عنصر x برابر k باشد (مثلا برای a این مقدار برابر ۳ است)، به ترتیب مکانهای k, mod ۷ (k+1), mod ۷ (k+2), تا mod ۷ (k+6), را بررسی میکنیم و x را در اولین مکان خالی قرار میدهیم. میدانیم j mod i باقیماندهی تقسیم صحیح عدد i بر عدد j است. به ازای ترتیبهای مختلف اضافه کردن عناصر g,…, b,a به جدول، کدامیک از حالتهای زیر نمیتواند حاصل شود؟
پاسخ
گزینه (۲) درست است.
در مورد گزینه (ب)٬ چون a در مکان ۶ قرار گرفته است معلوم میشود که قبل از آن مکانهای ۴٬۳ و ۵ پر بوده است که یکی از آنها یعنی مکان ۴ توسط f پر شده است٬ بنابراین f قبل از a وارد جدول شده است.
از طرف دیگر مکان اولیهی f خانه ۶ میباشد که هنگام ورود به جدول در صورت پر بودن آن خانه به یک خانه دیگر میرود. لحظه ورود عنصر f به جدول٬ خانه ۶ خالی بوده است و لزومی نداشت که به خانهی دیگر برود.
ترتیب ورود حروف به جدول در مورد گزینههای الف٬ ج و د به ترتیب به شکل زیر میتواند باشد:
الف: a⟶b⟶c⟶d⟶e⟶f⟶g
ج: a⟶c⟶e⟶g⟶b⟶d⟶f
د: a⟶d⟶e⟶f⟶c⟶g⟶b