معماهای مقید: شمارش حالت‌ها، پایستگی، دست‌یافتنی‌بودن و تعویض

معماهای مقید (constraint puzzles) دارای حالت، مجموعهٔ حرکت‌های مجاز و هدفی با چند شرط هستند. کمیت پایسته (invariant) کمیتی مانند جرم کل یا تعداد کل اشیاست که با هر حرکت مجاز ثابت می‌ماند. حالت شدنی (feasible state) همهٔ شرط‌ها را هم‌زمان برآورده می‌کند. معادله‌ای که یک کفه را متعادل یا یک طبقه را درست می‌کند، اگر با موجودی باقی‌مانده یا چیدمان نهایی ناسازگار باشد کافی نیست.

۱. کوچک‌ترین مدل مفید را بسازید

مشخص کنید که اشیای هم‌نوع متمایزند یا نه، آیا باید از همهٔ اشیا استفاده شود و آیا جایگاه‌ها برچسب دارند. این انتخاب‌ها تعیین می‌کنند چه چیزی یک پاسخ متفاوت محسوب می‌شود.

۲. ترازوهای آویخته: تکیه‌گاه بار هر دو کفهٔ پایین را حمل می‌کند

ترازوهای آرمانی با بازوهای برابر و جرم ناچیز را در نظر بگیرید. ترازوی پایین از زیر کفهٔ راست ترازوی بالا آویزان است. بار کفهٔ بالای چپ را $L$، وزنهٔ مستقیمِ کفهٔ بالای راست را $u$ و بار هر کفهٔ پایین را $s$ می‌گیریم. اگر جرم همهٔ وزنه‌ها $W$ باشد:

تکیه‌گاه پایین $2s$ را منتقل می‌کند، نه $s$. اگر جرم ترازو داده شده، آن را به بار منتقل‌شده اضافه کنید؛ اگر بازوها نابرابرند، به جای برابری جرم‌ها از تعادل گشتاور استفاده کنید. نخست مقادیر مجاز $u$ و $s$ را به دست آورید و سپس ترکیب‌ها را بشمارید.

مثال حل‌شدهٔ تعادل و شمارش

فرض کنید چهار وزنهٔ چهارواحدی، سه وزنهٔ دوواحدی و دو وزنهٔ یک‌واحدی داریم. باید از همهٔ وزنه‌ها استفاده شود، هیچ کفه‌ای خالی نباشد و کفهٔ بالای راست دقیقاً یک وزنه داشته باشد. کل جرم $W=24$ و در نتیجه $L=12$ است. با $u=4$، بار هر کفهٔ پایین $s=4$ و با $u=2$، این بار $s=5$ خواهد بود. انتخاب $u=1$ مستلزم $s=5.5$ است که با وزنه‌های صحیح امکان ندارد.

تعداد وزنه‌های چهار، دو و یک‌واحدی در کفهٔ پایین چپ را $x,y,z$ بگیرید. معادلهٔ $4x+2y+z=s$ را با رعایت موجودی پس از کنارگذاشتن $u$ حل کنید. ابتدا $x$ و سپس $y$ را بررسی کنید؛ جرم باقی‌مانده $z$ را تعیین می‌کند. این کار هم از حذف حالت و هم از تکرار ترتیب‌ها جلوگیری می‌کند.

پنج ترکیب متفاوت برای کفهٔ پایین چپ وجود دارد. کامل‌بودن فهرست روشن است: برای جرم چهار، یا یک وزنهٔ چهارواحدی داریم یا باید $2y+z=4$ را با حداکثر دو وزنهٔ یک‌واحدی حل کنیم؛ برای جرم پنج نیز یا $4+1$ داریم یا معادلهٔ $2y+z=5$ را حل می‌کنیم. هر سطر، تکمیلی شدنی برای همهٔ کفه‌ها دارد و صرفاً جرم کفهٔ پایین چپ درست نیست. اگر وزنه‌های مساوی نامتمایز باشند، بازنویسی $2+1+1$ به صورت $1+2+1$ ترکیب تازه‌ای نمی‌سازد.

شمارش فراتر از جدول موجودی

دسته‌های افزایشی (Monotone batches). در دور $j$، ابتدا $j$ شیء در چپ و سپس یکی در راست بگذارید. پس از $k$ دور کامل، موجودی مصرف‌شده $U_k=k(k+3)/2$ و تعداد راست $k$ است. اگر دستهٔ ناقص بعدیِ چپ به راست می‌رود، حالت‌های $1\le r\le k$ را با تعداد راست $k+r$ بررسی کنید. تمام‌شدن دقیق پس از هر یک از دو زیرمرحله را نیز بیازمایید: $U_k$ یا $U_k+(k+1)$. برای هدف چهار شیء در راست، کل‌های ممکن $7,10,14,19$ هستند: به‌ترتیب دو دور و دو باقی‌مانده، سه دور و یک باقی‌مانده، چهار دور کامل، یا چهار دور و دستهٔ بعدی چپ. افزایشی‌بودن، جست‌وجو را محدود می‌کند؛ دور کامل پنجم دیگر مجاز نیست.

شبکهٔ میانگین صحیح (Integer averaging networks). هر میانگین را به «دو برابر والد = مجموع فرزندان» تبدیل و رو به عقب جایگذاری کنید. با رأس $7$، میانهٔ $x,y$ و ردیف پایین $t,z,1$ داریم $x+y=14$، $2x=t+z$، $2y=z+1$ و بنابراین $t+2z=27$. برای برچسب‌های صحیح نامنفی تک‌رقمی، $z$ فرد است و $t\le9$ مقدارهای $z=9,t=9$ را تحمیل می‌کند؛ پس $y=5,x=9$. هر دو سطح را کنترل کنید. تکرار برچسب‌ها مجاز است، مگر تمایز تصریح شود.

افرازهای متقارن (Symmetric partitions). اگر قیدها و هدف هر دو متقارن‌اند، بگیرید $a\ge b\ge c\ge0$. برای $a+b+c=4$، حالت‌های $(4,0,0),(3,1,0),(2,2,0),(2,1,1)$ را بشمارید؛ مجموع مربع‌هایشان $16,10,8,6$ است. ابتدا کوچک‌ترین عضو را کران‌گذاری کنید. مقدارهای تکراری عبارت را نیز حذف کنید: برای مجموع شش، $(4,1,1)$ و $(3,3,0)$ هر دو مجموع مربع $18$ دارند. سه‌تایی مرتب، افراز و خروجی متمایز سه شمارش متفاوت‌اند؛ صفر را بی‌دلیل حذف نکنید.

برش‌های تو‌در‌تو (Nested cuts). برای طول‌های هم‌مبدأ $L_1<L_2<L_3$ و برش در $L_1\le x<L_2$، همهٔ قطعات مثبت عبارت‌اند از $L_1,x,L_2-x,x,L_3-x$. جسم کوتاهِ بریده‌نشده و هر دو قطعهٔ سمت چپ را نگه دارید. در $x=L_1$، کوتاه‌ترین جسم سالم می‌ماند؛ تکهٔ صفر قطعهٔ دیگری نیست. برای سه قطعهٔ برابر، بررسی کنید کدام طول دیگر با $x$ تکرارشده برابر است؛ اگر $x$ طول مشترک نیست، برابری سه طول دیگر را هم بیازمایید. جای برش و ترتیب طول‌ها را برای هر نامزد کنترل کنید.

برچسب جایگاه (Finite position labels). بین جایگاه‌های $p,q$ تعداد $\lvert p-q\rvert-1$ شیء قرار دارد. در ردیف دوازده‌تایی با ممنوعیت برچسب‌گذاری دو سر، حداکثر $11-2-1=8$ شیء بین دو برچسب است. شاهد کامل $B=2,D=6,A=7,C=11$ به هشت شیء بین B و C می‌رسد، چهار شیء بین A و B و چهار شیء بین C و D دارد و دقیقاً یک جفت برچسب مجاور، یعنی D و A، دارد. کران بالا به‌تنهایی دست‌یافتنی‌بودن را ثابت نمی‌کند.

۳. انتقال: اختلاف دو برابر تغییر می‌کند

انتقال $t$ شیء از چپ به راست، حالت $(a,b)$ را به $(a-t,b+t)$ تبدیل می‌کند. کل ثابت است، اما اختلاف چپ منهای راست به اندازهٔ $2t$ کاهش می‌یابد:

در مثالی مستقل، با انتقال چهار مهره از چپ به راست، تعدادها برابر می‌شوند. با تکرار همین حرکت، تعداد راست سه برابر چپ می‌شود. هر دو مرحله را نسبت به حالت اولیه ثبت کنید:

معادلهٔ نخست $a=b+8$ را می‌دهد. با جایگذاری در معادلهٔ دوم، $b+8=3b$ و در نتیجه $b=4$ و $a=12$ به دست می‌آید. مسیر حالت‌ها $(12,4)\to(8,8)\to(4,12)$ است. سهم اولیهٔ سمت راست $4/16=25\%$ است. بررسی کنید در هر حرکت، اشیای کافی برای انتقال وجود داشته باشد؛ دستگاهی که به تعداد منفی در یک مرحله برسد، پاسخ شدنی ندارد.

حرکت کسری و دست‌یافتنی‌بودن

برای اهدای کسرِ ساده‌شدهٔ $p/q$، اگر شکستن اشیا مجاز نیست، موجودی اهداکننده در همان مرحله باید بر $q$ بخش‌پذیر باشد. پیش از حرکت بعدی، همهٔ موجودی‌ها را به‌روز کنید؛ بخش‌پذیری اولیه به‌تنهایی کافی نیست. مثلاً اگر به‌ترتیب A، سپس B و سپس C نصف دارایی هر دو نفر دیگر را بگیرند، مسیر $(2,4,8)\to(8,2,4)\to(4,8,2)\to(2,4,8)$ مجاز است. موجودی هر اهداکنندهٔ واقعی زوج و کل $14$ ثابت است. برای کمینه، کران‌های پایینِ مربوط به هر مرحله را به دست آورید و مسیرِ رسیدن به آن‌ها را بسازید؛ شدنی‌بودن یک کل، کمینه‌بودنش را ثابت نمی‌کند.

قید پایستهٔ لازم فقط حالت‌ها را غربال می‌کند؛ ساخت کافی، دست‌یافتنی‌بودن را ثابت می‌کند. اگر هر حرکت به سه جایگاه دوبه‌دو نامجاور روی دایره، نفری یک شیء اضافه کند، بخش‌پذیری کل بر سه لازم است. دایره را شماره‌گذاری و یال اتصال آخر به اول را نیز کنترل کنید. در شش جایگاه، حرکت‌های $\{1,3,5\}$ و $\{2,4,6\}$ به‌طور مجاز در همهٔ جایگاه‌ها یک شیء می‌گذارند. جایگاه‌های شش و یک مجاورند؛ تکرار انتخاب مجاز نیز آزاد است، مگر ممنوع شود.

۴. کمینهٔ تعویض دلخواه: اثبات با چرخه‌ها

برای اشیای متمایز و هدف ثابت با جایگاه‌های مشخص، جایگاه اولیهٔ هر شیء را به جایگاه هدف آن نگاشت کنید. جایگشت حاصل را به چرخه‌های مجزا تجزیه کنید؛ برای اشیای درست نیز چرخه‌های تک‌عضوی را بشمارید. اگر $N$ جایگاه و $C$ چرخه داشته باشیم:

هر تعویض تعداد چرخه‌ها را حداکثر یک واحد افزایش می‌دهد؛ بنابراین برای رسیدن به $N$ چرخهٔ تک‌عضوی، دست‌کم $N-C$ تعویض لازم است. از طرف دیگر، چرخه‌ای با طول $k_i$ را می‌توان با $k_i-1$ تعویض حل کرد. پس کران پایین و ساخت عملی برابرند.

مثال: هدف $A,B,C,D,E,F$ و حالت اولیه $B,C,A,E,D,F$ است. نگاشت دارای چرخه‌های $(1\ 2\ 3)(4\ 5)(6)$ است؛ پس کمینه $6-3=3$ خواهد بود. جایگاه‌های یک و سه، سپس دو و سه و سپس چهار و پنج را عوض کنید. حالت‌ها به‌ترتیب $A,C,B,E,D,F$، سپس $A,B,C,E,D,F$ و در پایان هدف هستند.

دو کمینه می‌توانند متفاوت باشند: چیدمان $D,B,C,A$ با یک تعویض دلخواه به $A,B,C,D$ می‌رسد، اما پنج وارونگی دارد و پنج تعویض مجاور لازم دارد. اگر چند هدف نهایی مجاز است، هر هدف مرتبط را بررسی کنید و کمترین مقدار را بگیرید. برای تکرارهای نامتمایز، خود تطبیق با هدف هم باید انتخاب شود؛ یک برچسب‌گذاری دلخواه را کورکورانه مبنا قرار ندهید.

در معمای کفش یا اشیای جفتی، هم‌طبقه‌بودن را از جهت درست جدا کنید. قرارگرفتن هر دو عضو یک جفت در یک طبقه، خودبه‌خود به معنای الزام عضو چپ و راست به جایگاه فیزیکی معین نیست. شرط اضافی را فقط هنگامی اعمال کنید که مسئله آن را بیان کرده یا به‌روشنی پذیرفته باشد؛ وگرنه کمینه می‌تواند تغییر کند.

بهینه‌سازی تعویض با هدف ثابت، چیدمان را معلوم فرض می‌کند. کشف برچسب‌های نامعلوم با برداشت یا توزین، راهبرد مشاهده و کران بدترین حالت می‌خواهد؛ به کارت شناسایی و کدگذاری مراجعه کنید. مسیرهای جدولی و قیدهای شبکه نیز کارت همراه جداگانه دارند.

نکتهٔ کنکوری: ابتدا کمیت پایسته و هدف را مشخص کنید. سپس کمینه را با کران پایین و ساخت مجاز ثابت کنید، یا تعداد را با فهرست کامل و تکمیل شدنی برای هر سطر نشان دهید.

تلهٔ رایج: جرم درست یک کفه، موجودی باقی‌ماندهٔ کنترل‌نشده یا طبقه‌ای با برچسب‌های درست هنوز ممکن است هدف کامل را نقض کند. بار منتقل‌شده، کفه‌های غیرخالی، موجودی اشیا و جهتِ صریحاً لازم را کنترل کنید.