سوال ۲۲

ماشین «قارقوری» که برای نمایش اعداد طبیعی به‌کار می‌رود،از ۹ کلید و ۹ کارت‌‌خوان تشکیل‌ شده است. برای کار با «قارقوری»، ابتدا باید ۹ عدد صحیح مثبت روی ۹ کارت تمیز نوشته و در کارت‌خوان‌های ماشین قرار دهیم، سپس با روشن و خاموش کردن کلیدهای آن، به عدد موردنظر برسیم. می‌دانیم عددی که «قارقوری» به‌عنوان خروجی نمایش می‌دهد برابر است با: $n = s_1 \times v_1 + s_2 \times v_2 + ... + s_9 \times v_9$ که $v_i$ عدد نوشته‌شده روی کارت $i$ام بوده و مقدار $s_i$ درصورتی‌ که کلید $i$اُم روشن باشد برابر یک و درصورتی‌ که خاموش باشد، برابر منفی یک است.

وهاب قصد دارد از این ماشین برای نمایش اعداد طبیعی مختلف استفاده کند. می‌دانیم وهاب، مقادیر اولیه کارت‌ها را تنها یک‌بار و آن‌هم در آغاز کار با دستگاه می‌تواند تعیین کند و از آن به بعد صرفاً با تغییر وضعیت کلیدها قادر به تغییر مقدار خروجی خواهد بود. حداکثر مقدار $k$ را بیابید که وهاب بتواند طوری مقادیر کارت‌ها را در ابتدا تعیین کند که تنها با تغییر دادن حالت کلیدها قادر به نمایش تمام اعداد ۱ تا $k$ باشد.

  1. ۹
  2. ۸۱
  3. ۵۱۱
  4. ۱۹۶۸۲
  5. هیچ‌کدام

پاسخ

گزینه (۵) درست است.

با تغییر یکی از ضرایب $s_i$ها از ۱ به ۱- و یا از ۱- به ۱ زوجیت عدد $n$ تغییر نخواهد کرد٬ بنابراین اگر عددی مانند $\alpha$ توسط ماشین قابل نمایش باشد عدد $\alpha+1$ قابل نمایش نخواهد بود.