SpiDist

SpiDist از ترکیب Spider یعنی عنکبوت و Distance یعنی فاصله ساخته شده است.

چطور بازی کنیم؟

هر مرحله یک عنکبوت دارد: یک رأس مرکزی و چند «پا» که هر پا یک ردیف رأس است. تعداد مهره‌ها (k) و عدد هدف (D) را مرحله تعیین می‌کند. باید مهره‌ها را طوری بگذارید که فاصله‌ی جفت‌مهره‌ها همه‌ی عددهای ۱ تا D را بسازند.

در مرحله‌هایی که «خط‌کش کامل» می‌خواهند، هر فاصله باید دقیقاً یک بار بیاید. در بقیه‌ی مرحله‌ها تکرار اشکالی ندارد. فاصله‌های بزرگ‌تر از D هم مانعی ندارند، ولی به کار هم نمی‌آیند.

مرحله‌ها

مرحلهپاهاkDهدف
۱. خط‌کش ساده۶۴۶خط‌کش کامل
۲. خط‌کش بلندتر۹۵۹پوشش، تکرار مجاز
۳. اولین عنکبوت۳، ۳، ۳۴۶خط‌کش کامل
۴. سه پای نابرابر۵، ۴، ۳۵۹پوشش، تکرار مجاز
۵. رکورد خط را بشکنید۶، ۵، ۹، ۱۶۱۵خط‌کش کامل
۶. قفل زوجیت۵، ۵، ۵۵۱۰خط‌کش کامل، یا دلیل اینکه ممکن نیست
۷. هفت مهره۹، ۱۱، ۸۷۲۰پوشش، تکرار مجاز
۸. هشت مهره۱۱، ۲، ۱۲، ۱۳۸۲۵پوشش، تکرار مجاز
؟ مرز پژوهششش پای ۱۳۸۲۶مسئله‌ی باز

در مرحله‌ی ۶ اگر فکر می‌کنید ساختن خط‌کش کامل ممکن نیست، دکمه‌ی «به نظرم ممکن نیست!» را بزنید. بازی یک سؤال کوتاه می‌پرسد و اگر دلیلش را درست بگویید، مرحله حل می‌شود. اگر مرحله‌ی آخر را حل کنید، مختصات مهره‌ها را می‌بینید و می‌توانید کپی کنید.

برای معلم‌ها و دانشجوها

خط‌کش تُنُک و خط‌کش کامل

روی خط، k علامت حداکثر k(k−1)/2 جفت می‌سازند. اگر این جفت‌ها همه‌ی فاصله‌های ۱ تا D را بسازند، یک «خط‌کش تُنُک» داریم، و اگر هر فاصله دقیقاً یک بار بیاید، یک «خط‌کش کامل». روی خط، خط‌کش کامل فقط تا ۴ علامت وجود دارد (۰، ۱، ۴، ۶). بیشترین طولی که با ۵، ۶، ۷ و ۸ علامت روی خط پوشیده می‌شود، به ترتیب ۹، ۱۳، ۱۷ و ۲۳ است؛ این عددها را بازی پیش از هر انتشار با جست‌وجوی کامل دوباره بررسی می‌کند.

چرا عنکبوت؟

روی یک درخت، فاصله‌ی دو رأس طول تنها مسیر میان آن‌هاست. عنکبوت ساده‌ترین درختی است که از خط فراتر می‌رود: فاصله یا تفاضلی است (یک پا) یا جمعی (دو پا). همین دوگانگی اجازه می‌دهد که مثلاً ۶ مهره، که روی خط فقط تا ۱۳ را می‌پوشانند، روی یک عنکبوت خط‌کش کاملِ ۱ تا ۱۵ بسازند (مرحله‌ی ۵).

قفل زوجیت

عنکبوت گرافی دوبخشی است: رأس‌ها را بر اساس زوج یا فرد بودن عمق دو رنگ کنید. فاصله‌ی دو رأس فرد است اگر و تنها اگر رنگشان فرق کند. با ۵ مهره، اگر s مهره یک رنگ باشند، s(5−s) فاصله‌ی فرد داریم که فقط ۰، ۴ یا ۶ است، ولی خط‌کش کامل ۱ تا ۱۰ به دقیقاً ۵ فاصله‌ی فرد نیاز دارد. در حالت کلی اثبات می‌شود که خط‌کش کامل روی گراف دوبخشی فقط وقتی ممکن است که k به شکل t² یا t²+2 باشد. به همین دلیل ۷ مهره حداکثر ۱ تا ۲۰ و ۸ مهره حداکثر ۱ تا ۲۷ را می‌پوشانند.

برچسب‌گذاری دلپذیر

مرحله‌ی ۱ پلی است به یکی از معروف‌ترین حدس‌های نظریه‌ی گراف: حدس برچسب‌گذاری دلپذیر (graceful labeling) می‌گوید رأس‌های هر درخت با n یال را می‌شود با عددهای متمایز ۰ تا n برچسب زد طوری که تفاضل دو سر یال‌ها دقیقاً ۱ تا n شود. این حدس هنوز اثبات نشده است.

مسئله‌ی باز

بهترین جواب شناخته‌شده برای ۸ مهره روی درخت، پوشش ۱ تا ۲۵ است (مرحله‌ی ۸). قفل زوجیت می‌گوید بیشتر از ۲۷ ممکن نیست. اینکه ۲۶ یا ۲۷ ممکن است یا نه، تا جایی که می‌دانیم هنوز باز است. مرحله‌ی آخر همین سؤال را روی عنکبوتی با شش پای ۱۳ تایی می‌پرسد. اگر جوابی پیدا کردید، مختصات مهره‌ها را کپی کنید و برای ما بفرستید.

بازی کنید