یک جایگشت مرتبهی n دنبالهای (ترتیبی) از اعداد ۱ تا n است. برای مثال ⟨۳,۱,۴,۲⟩ یک جایگشت مرتبهی ۴ است. جدول ضرب یک جایگشت P=⟨p1,p2,...,pn⟩ یک جدول n×n است که مقدار خانهی سطر iاُم و ستون jاُم آن برابر pi×pj میباشد. برای مثال٬ جدول ضرب جایگشت ⟨۳,۱,۲⟩ به صورت شکل مقابل است.
آیدا و آیدین بازی زیر را انجام میدهند. ابتدا آیدین از اتاق بیرون میرود و آیدا یک جایگشت مرتبهی ۸ انتخاب میکند و جدول ضرب آن را مینویسد و بر روی هر کدام از ۶۴ خانهی جدول یک سکه میگذارد.
آیدین به اتاق برمیگردد و k تا از خانههای جدول را انتخاب میکند و از آیدا میخواهد تا سکههای آن k خانه را همزمان از روی صفحه بردارد. بعد از انجام این کار٬ اگر آیدین بتواند جایگشت آیدا را دقیقا تعیین کند٬ برنده میشود. کمترین مقدار k که آیدین بتواند همواره برنده بشود چند است؟
پاسخ
گزینه (۳) درست است.
۶ سوال لازم و کافی است.
مثال: فرض کنید ضرب عدد اول با اعداد سوم و چهارم را بپرسیم. همچنین ضرب عدد دوم با اعداد پنجم تا هفتم را بپرسیم و در نهایت ضرب اعداد هفتم و هشتم را نیز بپرسیم (در مجموع شش پرسش انجام دادهایم).
اگر چهار پرسش اول را در پرسش ششم ضرب کنیم و حاصل را P بنامیم، داریم:
P=p12×p22×p3×…×p8
در نتیجه اگر عدد حاصل را بر 8! تقسیم کنیم حاصل برابر p1×p2 میشود. حال اگر هر سه پرسش با جایگشت متفاوت را در هم ضرب کنیم ضرب دو عنصر دیگر (همانند قبلی) بدست میآید. بدین ترتیب میتوان ضرب اعداد سوم و چهارم با اعداد پنجم و ششم را متوجه شد.
به همین روند میتوان ضرب عدد اول و هفتم را فهمید. در نتیجه چون ضرب هر دوتایی از اعداد اول و ششم و هفتم را داریم میتوان هرکدام از آنها را بهدست آورد. پس چون ضرب دوتایی این اعداد را داریم هر عدد نیز به صورت مستقل بهدست خواهد آمد.