خلاصه مقاله:
- مسئلهی آویزانکردن تابلو از سؤالی ساده شروع شد: آیا میتوان نخ پشت تابلو را طوری دور میخها پیچید که رفتار مشخصی هنگام برداشتن میخها داشته باشد؟ این مسئله در سال ۱۹۹۷ توسط اِی. اسپیواک مطرح شد و بعدها به خانوادهای از مسائل ریاضی با نام «مسائل آویزانکردن تابلو» تبدیل شد.
- در نسخهی اصلی، هدف این است که نخ طوری طراحی شود که هر دو میخ برای نگهداشتن تابلو ضروری باشند و حذف هرکدام باعث تغییر وضعیت آویزان بودن تابلو شود. با افزایش تعداد میخها، مسئله پیچیدهتر میشود؛ چون نخ باید برای تمام ترکیبهای ممکنِ برداشتن میخها عملکرد درست داشته باشد.
- ریاضیدانان ثابت کردهاند که برای هر مسئلهی «k از n» میتوان یک آرایش نخ پیدا کرد، اما پیداکردن کوتاهترین راهحل بسیار دشوار است. در مسئلهی «۲ از ۴»، پژوهشگران با کمک الگوریتمهای کامپیوتری ثابت کردند که حداقل ۱۶ بار پیچاندن نخ برای حل این مسئله لازم است.
فرض کنید میخواهید تابلویی را با نخی که پشت آن بسته شده، روی دو میخ آویزان کنید. سادهترین راه این است که نخ را روی هر دو میخ بیندازید. در این حالت، اگر یکی از میخها را از دیوار بیرون بکشید، تابلو معمولاً همچنان از میخ دیگر آویزان میماند.
اما ریاضیدانان سالهاست نسخهای عجیبتر از همین مسئله ساده را بررسی میکنند: آیا میشود نخ را آنقدر حسابشده دور دو میخ پیچید که با برداشتن هرکدام از آنها، کل سیستم از هم باز شود و تابلو بیفتد؟ این سؤال در سال ۱۹۹۷ از سوی اِی. اسپیواک مطرح شد و خیلی زود به خانوادهای از مسائل ریاضی تبدیل شد که امروز با نام «مسائل آویزانکردن تابلو» شناخته میشوند.
ظاهر مسئله ساده و حتی سرگرمکننده است، اما پشت آن مجموعهای از ایدههای جدی در ریاضیات از نظریه گرهها و نظریه گروهها گرفته تا نظریه گراف و منطق بولی قرار دارد.
مسئله آویزانکردن تابلو چیست؟
در سادهترین حالت، دو میخ روی دیوار داریم و یک نخ که به پشت تابلو متصل است. هدف این نیست که تابلو را فقط محکم آویزان کنیم. برعکس، باید نخ را طوری دور میخها بیندازیم که هر دو میخ برای نگه داشتن تابلو ضروری باشند. یعنی اگر میخ اول برداشته شود، تابلو بیفتد و اگر میخ دوم هم بهتنهایی برداشته شود، باز تابلو سقوط کند.
نکته اصلی اینجاست که نخ نباید صرفاً به دو تکیهگاه مستقل متصل باشد. مسیر آن باید طوری طراحی شود که حذف هر میخ، آرایش کل نخ را باز کند. این مسئله را میتوان با چند حلقه و پیچ ساده حل کرد، اما وقتی تعداد میخها بیشتر شود، شرایط خیلی پیچیدهتر میشود.
تام ورهوف، دانشمند بازنشسته علوم کامپیوتر، این نوع مسائل را در یک کارگاه آموزشی برای دانشآموزان بررسی کرد. شرکتکنندگان با نخ و کارابینهای واقعی آزمایش میکردند، اما همزمان تلاش داشتند مسئله را با زبان ریاضی هم توصیف کنند.
ریاضیدانان بعداً نسخه کلیتری از مسئله را مطرح کردند که با عنوان «k از n» شناخته میشود. در این حالت، n تعداد کل میخها است و k تعداد میخهایی که باید برداشته شوند تا تابلو سقوط کند. برای مثال، در مسئله «۲ از ۴»، چهار میخ روی دیوار وجود دارد و نخ باید طوری پیچیده شود که برداشتن هر دو میخ از میان این چهار میخ باعث سقوط تابلو شود. در عین حال، اگر فقط یک میخ برداشته شود، تابلو باید همچنان آویزان بماند. این شرط موضوع را بسیار دشوار میکند، چون نخ باید برای تمام ترکیبهای ممکن رفتار درستی داشته باشد.
راهحل وجود دارد، اما ممکن است بسیار پیچیده باشد
در سال ۲۰۱۲، ریاضیدانان در مقاله پیشچاپی نشان دادند که برای هر مسئله از نوع «k از n» میتوان راهحلی پیدا کرد. به بیان ساده، از نظر ریاضی امکان طراحی آرایشی از نخ وجود دارد که دقیقاً همان قانونی را اجرا کند که برای افتادن تابلو تعریف کردهایم.
اما وجود راهحل به این معنا نیست که آن راهحل ساده یا کوتاه باشد. بعضی از روشهای شناختهشده به تعداد زیادی پیچیدن نخ دور میخها نیاز دارند و اگر بخواهیم چنین چیزی را در دنیای واقعی اجرا کنیم، نتیجه بیشتر شبیه یک گره بزرگ و درهمپیچیده خواهد بود تا روشی منطقی برای نصب تابلو. همین مسئله باعث شد ورهوف و دیگران به سؤال دیگری برسند: کوتاهترین راهحل ممکن چیست؟
در یکی از کارگاهها، ورهوف و شرکتکنندگان سراغ مسئله «۲ از ۴» رفتند. کوتاهترین راهحل شناختهشده در آن زمان به ۸۰ بار پیچاندن نخ دور میخها نیاز داشت. آنها توانستند تعداد پیچشها را به ۵۸ کاهش دهند.
ورهوف بعداً این مسیر را ادامه داد و راهحلی با فقط ۱۸ پیچش پیدا کرد. اما هنوز مشخص نبود آیا ۱۸ واقعاً حداقل مقدار ممکن است یا میشود باز هم بهتر عمل کرد.
برای پاسخ قطعی، او با ینس هویسولت، که آن زمان دانشجوی دکتری بود، همکاری کرد. آنها از برنامههای کامپیوتری استفاده کردند تا تمام آرایشهای کوتاهتر ممکن را بررسی کنند. نتیجه این بررسی نشان داد که هیچ راهحلی با کمتر از ۱۶ پیچش وجود ندارد.
در نتیجه، ۱۶ پیچش حداقل مطلق برای حل مسئله «۲ از ۴» است.
این بخش از کار اهمیت زیادی دارد، چون پیدا کردن یک راهحل کوتاه با ثابت کردن اینکه هیچ راهحل کوتاهتری وجود ندارد فرق دارد. برای اثبات حداقل بودن، باید نشان داد تمام حالتهای ممکن با ۱۵ پیچش یا کمتر شکست میخورند؛ کاری که بررسی دستی آن بسیار دشوار است و برنامه کامپیوتری میتواند کمک بزرگی باشد.
ورهوف ابتدا برنامهای نوشته بود که میتوانست این مسئله را در حدود دو ساعت حل کند. هویسولت بعداً برنامهای ساخت که همان کار را در حدود دو ثانیه انجام میداد.
مسئله آویزانکردن تابلو فقط یک معمای ریاضی نیست و به طراحی الگوریتمهای کارآمد هم مربوط میشود. هرچه تعداد میخها و شرایط بیشتر شوند، تعداد حالتهایی که باید بررسی شوند بهسرعت افزایش پیدا میکند. بنابراین یافتن راهی هوشمندانه برای حذف حالتهای اضافی، بخشی مهم از مسئله است.
ورهوف نتایج این پژوهش و کوتاهترین راهحلهای شناختهشده برای خانواده بزرگی از این مسائل را در arXiv منتشر کرده است.
فرض کنید یک تابلو را با یک نخ از دو میخ روی دیوار آویزان کردهاید. شکل نخ طوری است که اگر هر کدام از میخها را جدا کنید، تابلو از دیوار میافتد. اما هدف این معما این است: چطور نخ را دور دو میخ ببندیم که اگر هر کدام از میخها را برداریم، تابلو همچنان روی دیوار بماند؟
در این روش، نخ بهجای اینکه فقط یک بار دور هر میخ پیچیده شود، یک مسیر خاص را طی میکند: ابتدا به دور میخ اول (a) و سپس به دور میخ دوم (b) در جهت عقربههای ساعت میپیچد. بعد دوباره همین مسیر را در جهت مخالف طی میکند؛ یعنی یک بار دیگر دور میخ اول و دوم، اما خلاف جهت عقربههای ساعت قرار میگیرد. به این ترتیب، مسیر نخ را میتوان به شکل +a +b -a -b نمایش داد. علامت مثبت و منفی نشان میدهد نخ در هر جهت چند بار دور هر میخ پیچیده شده است. اگر میخ a را بیرون بکشیم، بخشهای مربوط به آن یعنی +a و -a همدیگر را خنثی میکنند و از مسیر نخ حذف میشوند؛ اما بخشهای باقیمانده یعنی +b و -b همچنان نخ را به میخ دوم متصل نگه میدارند. همین اتفاق برای میخ b هم رخ میدهد. در نتیجه، برداشتن هر کدام از دو میخ باعث آزاد شدن کامل نخ نمیشود، چون میخ دیگر هنوز مسیر نخ را نگه داشته است. این ترفند ساده باعث میشود تابلو حتی با حذف یکی از دو نقطهی اتصال، همچنان روی دیوار باقی بماند.
چرا ریاضیدانان وقتشان را صرف چنین مسئلهای میکنند؟
در نگاه اول شاید ماجرا کمی بیهوده به نظر برسد. چرا باید کسی ساعتها یا حتی سالها وقت بگذارد تا بفهمد چگونه میتوان یک تابلو را به بدترین و پیچیدهترین شکل ممکن روی دیوار آویزان کرد؟
پاسخ این است که ریاضیدانان معمولاً فقط به ظاهر فیزیکی مسئله نگاه نمیکنند. برای آنها، میخها و نخها نماینده ساختارهای انتزاعی هستند.
مسیر نخ میتواند بهصورت یک عبارت ریاضی، یک گراف، مسیری روی یک شکل چندبعدی یا حتی ساختاری منطقی نمایش داده شود. به همین دلیل، این مسئله با چند شاخه مهم ریاضیات ارتباط پیدا میکند.
یکی از حوزههای مرتبط، نظریه گروهها است. در این شاخه از ریاضیات، پژوهشگران بررسی میکنند که چگونه مجموعهای از عملیات مختلف میتواند با هم ترکیب شود و چه قوانینی بر این ترکیبها حاکم است.
- 9 روز قبلمطالعه '19
- 28 بهمن 03مطالعه '5
- 31 اردیبهشت 05مطالعه '2
- 20 اسفند 04مطالعه '18
در مسئله آویزانکردن تابلو، پیچیدن نخ دور هر میخ را میتوان به یک عمل خاص تبدیل کرد. ترتیب پیچها و جهت آنها نیز اهمیت دارد. وقتی یک میخ برداشته میشود، بعضی از این عملیات عملاً حذف میشوند و سؤال این است که آیا چیزی از آرایش نخ باقی میماند یا کل آن باز میشود. همین ویژگی باعث میشود مسئله با نظریه گروهها ارتباط پیدا کند.
نظریه گرهها هم طبیعی است که وارد ماجرا شود، چون اساس مسئله به نحوه پیچیدن و حلقهزدن نخ مربوط میشود. در نظریه گرهها، ریاضیدانان بررسی میکنند که حلقهها و رشتهها چگونه به هم پیچیدهاند و تحت چه تغییراتی میتوان آنها را باز کرد یا به شکل دیگری تبدیل کرد.
تقریباً هر قانون منطقی را میتوان با نخ اجرا کرد
یکی دیگر از جنبههای جالب مسئله این است که میتوان برای مجموعه بزرگی از قوانین مختلف، یک آرایش مناسب از نخ پیدا کرد.
فرض کنید چهار میخ داریم و میخواهیم تابلو فقط در شرایط خاصی سقوط کند. مثلاً شاید بخواهیم با برداشتن هر دو میخ سقوط کند، یا فقط زمانی بیفتد که سه میخ مشخص حذف شده باشند.
اما هر قانونی ممکن نیست. برای نمونه، نمیتوان قانونی تعریف کرد که بگوید اگر فقط میخ A برداشته شود، تابلو سقوط کند، اما اگر هم میخ A و هم میخ B را برداریم، تابلو دوباره آویزان بماند. دلیلش ساده است: برداشتن میخ بیشتر نمیتواند ناگهان حمایت تازهای برای تابلو ایجاد کند. اگر حذف A برای سقوط کافی بوده، حذف A و B هم باید باعث سقوط شود. این ویژگی در ریاضیات با مفهوم توابع بولی یکنوا ارتباط دارد.
تابع بولی در سادهترین حالت تابعی است که ورودیهایش فقط دو حالت دارند؛ مثلاً «بله یا خیر»، «روشن یا خاموش» یا «میخ هست یا میخ نیست». خروجی هم دو حالت دارد؛ مثلاً «تابلو میماند» یا «تابلو میافتد».
وقتی میگوییم یک تابع بولی «یکنوا» است، یعنی اگر حذف تعداد مشخصی از میخها باعث سقوط شده باشد، حذف میخهای بیشتر نمیتواند دوباره تابلو را نجات دهد. این همان منطقی است که بهطور طبیعی در مسئله آویزانکردن تابلو وجود دارد.
جالبتر اینکه توابع بولی یکنوا فقط ابزار بازی با میخ و نخ نیستند و در حوزههایی مانند رمزنگاری، علوم کامپیوتر و نظریه رأیگیری هم کاربرد دارند. برای مثال، در یک سیستم رأیگیری میتوان پرسید چه ترکیبی از رأیها برای تصویب یک تصمیم کافی است. در یک سیستم امنیتی هم ممکن است ترکیبی از چند شرط برای دادن دسترسی لازم باشد. از این زاویه، مسئله تابلو یک نمونه فیزیکی و ملموس از ساختارهای منطقی پیچیده است.
شاید سؤال «چه کاربردی دارد؟» سؤال درستی نباشد
با وجود تمام این ارتباطها، ورهوف معتقد است حتی لازم نیست برای چنین مسئلهای حتماً کاربرد فوری پیدا کنیم. بخش بزرگی از ریاضیات و علوم در ابتدا از روی کنجکاوی شکل گرفته است. بعضی از ایدههایی که زمانی کاملاً نظری و بیکاربرد به نظر میرسیدند، سالها یا دههها بعد به ابزارهایی مهم تبدیل شدند.
ورهوف این موضوع را با استعارهای درباره آینده بشر توضیح میدهد. از نظر او، ما دقیقاً نمیدانیم در آینده با چه مسائلی روبهرو خواهیم شد و به چه دانشی نیاز پیدا خواهیم کرد. به همین دلیل، بازیکردن با ایدهها، طرح سؤالهای عجیب و بررسی مسائلی که در ظاهر هیچ فایده مستقیمی ندارند، بخشی از فرایند یادگیری است.
مسئله آویزانکردن تابلو نمونه خوبی از همین نوع کنجکاوی است: یک سؤال ساده درباره چند میخ و یک تکه نخ که در نهایت به نظریه گروهها، گرهها، گرافها، هندسه چندبعدی، منطق و الگوریتمهای کامپیوتری میرسد.
