راه حل‌قسمت ساده

فرض کنید عدد هر کارت بین ۱ تا ۱۳ باش (سرباز =۱۱، بیبی =۱۲ و شاه =۱۳). ترتیب دوری هم یعنی اینکه کارت بعدی ۱۳، کارت ۱ است. مثلا ۵ کارت بعد از کارت ۱۰ ام می‌شود کارت ۲.

از ۵ کارتی که جادوگر به دنا می‌دهد، طبق اصل لانه‌ی کبوتری حداقل دو کارت علامت یکسان دارند. دنا ۲ کارت با علامت یکسان را انتخاب می‌کند (در صورت وجود بیش از ۲ کارت با این خاصیت، ۲ کارت دلخواه انتخاب می‌شوند) ، از بین این دو کارت با علامت یکسان، شماره‌ی یکی (کارت الف) به صورت دوری در ۶ تای بعدی اون یکی کارت (کارت ب) قرار داد.

دنا کارت الف را رو به پایین می‌گذارد (یعنی کارتی که تارا باید حدس بزند). و کارت ب را به عنوان اولین کارت به تارا نشان می‌دهد.

اختلاف به صورت دوری شماره این ۲ کارت را هم که بین ۱ تا ۶ است، با جایگشت ۳ کارت باقیمانده نمایش می‌دهد.

تارا با دیدن کارت اول علامت کارت پنهان رو می‌تواند تشخیص دهد، و با دیدن شماره کارت اول و جایگشت ۳ کارت دیگر، شماره کارت پنهان را.

پس با این استراتژی تارا و دنا می‌توانند همیشه بر جادوگر پیروز شوند.

چند مثال با فرض اینکه علامت رو با A,B,C,D و شماره رو با ۱..۱۳ نشون بدیم:

مثال ۱.

• ۵ کارتی که جادوگر انتخاب کرده: A3, C6, B11, A7, D8
• ۲ کارت با علامت یکسان که تارا انتخاب می‌کند: A3 و A7
• دنا A7 را رو به پایین می‌گذارد.
• ۶ جایگشت ۳ کارت باقیمانده به صورت مرتب شده: [B11,C6,D8], [B11,D8,C6], [C6,B11,D8], [C6,D8,B11], [D8,B11,C6], [D8,C6,B11].
• پس دنا کارت‌هایی که به تارا نشان می‌دهد به ترتیب: A3,C6,D8,B11
• تارا با دیدن کارت اول متوجه می‌شود علامت کارت رو به پایین A است.
• تارا با دیدن C6,D8,B11 متوجه می‌شود عدد کارت رو به پایین ۴ تا بعد از عدد A3 است.
• پس تارا تشخیص می‌دهد که کارت رو به پایین A7 است.

مثال ۲.

• ۵ کارتی که جادوگر انتخاب کرده: A11,B11,B1,B5,C5
• ۲ کارت باعلامت یکسان که تارا انتخاب می‌کند: B11, B1. عدد B1 سه تا بعد از عدد B11 به صورت دوری قرار دارد (۱۱ .. ۱۲ .. ۱۳ .. ۱)
• دنا B1 را رو به پایین می‌گذارد.
• ۶ جایگشت ۳ کارت باقیمانده به صورت مرتب شده: [A11,B5,C5], [A11,C5,B5], [B5,A11,C5], [B5,C5,A11], [C5,A11,B5], [C5,B5,A11].
• پس دنا کارت‌هایی که به تارا نشان می‌دهد به ترتیب: B11,B5,A11,C5.
• تارا با دیدن کارت اول متوجه می‌شود علامت کارت رو به پایین B است.
• تارا با دیدن B5,A11,C5 متوجه می‌شود عدد کارت رو به پایین ۳ تا بعد از عدد B11 است.
• پس تارا تشخیص می‌دهد که کارت رو به پایین B1 است.

راه‌حل‌ قسمت چالشی

یک گراف دو بخشی را در نظر بگیرید که یک بخش آن شامل c(52,n) راس میباشد. هر راس آن بخش نماینده انتخاب n کارت از 52 کارت مسئله هست.

در بخش دیگر تعداد رئوس برابر با !c(52,k) *k و‌هر‌راس نماینده یک جایگشت k تایی از ۵۲ کارت مسئله است.

هر راس x بخش اول به تمام رئوس y از بخش دوم یال دارد که همه k کارت متناظر با راس y در‌بین‌ n کارت متناظر با راس x باشد.

تعداد یال های هر راس بخش اول برابر است با !c(n,k) * k و تعداد یال های هر راس بخش دوم برابر است با c(52-k,n-k).

چون گراف ساخته شده یک گراف دو بخشی است که درجه رئوس هر بخش با هم برابر است پس یک تطابق بین رئوس این گراف وجود دارد که تمام رئوس بخش کوچکتر را پوشش می‌دهد.

برای اینکه دنا و تارا بتوانند برنده شوند، باید به ازای هر جایگشت k تایی بتوانند سر یک انتخاب n تایی که شامل آن k کارت است توافق کنند. پس هر استراتژی دنا و تارا معادل یک تطابق در این گراف است که تمام رئوس بخش اول را پوشش میدهد پس در صورتی دنا و تارا میتوانند برنده بازی شوند که تعداد رئوس بخش اول کمتر یا مساوی تعداد رئوس بخش دوم باشد.

پس دنا و تارا در صورتی میتوانند حادوگر را شکست دهند که !c(52,n) <= c(52,k) * k