مهمة اللغز "tag" هي ترتيب البلاط المرقّم. اليوم ، حل علماء الرياضيات المشكلة العكسية - كيفية خلط اللغز.ربما لعبت العلامة. هذه لعبة محبطة ولكنها تسبب الإدمان وتتكون من 15 مربعًا ومساحة فارغة واحدة ، مرتبة في شبكة 4 × 4. المهمة هي نقل البلاط وترتيبها بترتيب تصاعدي للأرقام أو ، في بعض الإصدارات ، تجميع صورة منها.
بعد ظهورها في سبعينيات القرن التاسع عشر ، دخلت المجموعة القياسية من الألعاب. بالإضافة إلى ذلك ، اجتذبت انتباه علماء الرياضيات الذين درسوا الألغاز من مختلف الأحجام والتكوينات الأولية لأكثر من قرن.
يوجد اليوم
دليل جديد على حل "اللعبة عند 15" ، ولكن بترتيب عكسي. قرر عالم الرياضيات يون تشو
وروبرت هاو من جامعة ستوني بروك عدد الحركات اللازمة لتحويل حقل مرتب إلى حقل عشوائي.
اقترح
Percy Deaconess نسخة من مشكلة "العلامة" في التوزيع العشوائي في عام 1988. اقترح أن العشوائية الألغاز من أي حجم يتطلب حوالي
3 حركات. هذا يعني ، بالنسبة للحقل 4 × 4 ، ستكون هناك حاجة إلى 4
3 أو 64 حركة ، وللحقل 10 × 10 ، 10
3 ، أو 1000 حركة. (على الرغم من أنها لا تزال يشار إليها باسم "خمسة عشر ،" يمكن أن تحتوي الحقول على أي عدد من المسافات التي تشكل المربع الصحيح.)
اقترح عالم الرياضيات في جامعة ستانفورد ، الشماسة ، أن روايته لمشكلة "15 لعبة" تمثل فئة كبيرة من القضايا العشوائية المماثلة. ترتبط العديد من هذه المهام بالسمات الأساسية للطبيعة ، على سبيل المثال ، مع تغيير أماكن أزواج الدنا الأساسية التي تسبب طفرة جينية ، وكيف يتم فصل الجزيئات عن بعضها البعض وتصبح مختلة - يحدث هذا عندما يذوب الجليد.
كانت الشماسة تأمل في أن تكون قد فهمت مشكلة تشابك "البقع" ، فسنكون قادرين على فهم كيف تتحول الأنظمة المرتبة ككل إلى حالة مختلطة بشكل موحد.
في مواقف مثل "العلامة" العشوائية تطور خطوة واحدة في وقت واحد. تخيل حقلًا مرتبًا بالكامل ، مع وجود وحدة في الجزء العلوي الأيسر ومساحة فارغة في أسفل اليمين. نقوم بنقل البلاط بحيث تتحرك المساحة الفارغة مربعًا واحدًا في أي من الاتجاهات الأربعة المحتملة: أعلى أو أسفل أو يسار أو يمين. (من أجل الأناقة الرياضية ، نظر Chu و Howe في حقل ترتبط حوافه ببعضهما البعض في حلقة ، وبالتالي لا تتعثر البلاط في الزوايا.) فلنقم باختيار عشوائي. الآن الحقل في تكوين جديد - ليس تمامًا في أمر ، لكن ليس بعيدًا عنه. كرر هذه العملية. إذا واصلت تحريك المربع الفارغ ، فسيتم نقل الحقل بشكل متزايد بعيدًا عن الموقع الأصلي الذي تم طلبه.
تتمثل إحدى الميزات المهمة لهذه العملية في أن تكوين الحقل التالي في كل خطوة يعتمد فقط على التكوين الحالي. هذا يذكرنا بأحد ألعاب Monopoly: إن احتمال رمي الزهر ونقل مربعين من Park Place إلى Boardwalk لا يعتمد على القوائم التي أدت بنا إلى قفص Park Place.
تزحف الخمسة عشر تزحفًا نحو الاضطراب تدريجيًا ، خطوة واحدة في كل مرة. العديد من الأنظمة الأخرى ، مثل ذوبان الجليد ، عشوائية بطريقة واحدة. يدرس علماء الرياضيات هذه الظاهرة باستخدام نماذج تسمى "سلاسل ماركوف". سلاسل Markov هي طريقة رسمية لدراسة أي عملية عشوائية تعتمد فيها تهيئة النظام اللاحقة فقط على التكوين الحالي. هم في طليعة الفهم الرياضي للصدفة.
يقول عالم الرياضيات يوفال بيريز ، الذي قام بعمل مهم في نظرية الاحتمالات: "سلاسل ماركوف في الوسط الذهبي - فمن ناحية ، لا يزال بإمكاننا تحليلها ، من ناحية أخرى ، فهي تصف العديد من الظواهر التي تهمنا".
في عملهم الجديد ، عمل Chu and Howe مع التوزيع العشوائي لـ "tag" كما هو الحال مع سلسلة Markov. على وجه الخصوص ، نظروا في مجموعة من الأرقام تسمى "مصفوفة الانتقال" لسلسلة ماركوف. مصفوفة الانتقال عبارة عن مجموعة واسعة من الأرقام التي تحدد احتمال انتقال "لعبة في 15" من تكوين إلى آخر إذا قررنا نقل مساحة فارغة عشوائيًا.
إن فهم مصفوفة الانتقال هو مفتاح حساب عدد الحركات اللازمة لإضفاء الطابع العشوائي على حقل مرتب أو تبديله. على وجه الخصوص ، ركز تشو وهوي على تحديد مجموعة الأرقام التي تميز مصفوفة الانتقال - الأرقام التي تسمى "القيم الذاتية".
يقول هاو: "من خلال جمع معلومات كافية عن القيم الذاتية ، يمكننا الحصول على معلومات خلط دقيقة للغاية".
تحتوي مصفوفة الانتقال الخاصة بـ "البقع" على كمية هائلة من المعلومات التي تعكس تريليونات من التكوينات المختلفة التي يمكن أن ينشئها حقل صغير 4 في 4. هذه معلومات أكثر مما يستطيع علماء الرياضيات معالجتها مباشرة. لذلك ، بدلاً من تحليل مصفوفة الانتقال في كل خطوة من مسار الحقل إلى التوزيع العشوائي ، اكتشف Chu و Howe كيفية تحديد متوسط سلوك مصفوفة الانتقال بأكملها طوال الرحلة.
تشبه مقاربتهم كيف يمكنك معرفة المكان الذي من المرجح أن ينتهي بنا فيه الأمر في حقل Monopoly بعد 1000 لفة نرد: في الواقع يمكنك لف النرد عدة مرات ، أو يمكنك فقط أخذ متوسط عدة لفات واستنباطها.
باستخدام هذه التقنية ، قام Chu and Howe بحساب القيم الذاتية لمصفوفة الانتقال ، والتي أخبرتهما عن عدد الخطوات التي يلزم إجراؤها لتخصيص العشوائية لـ "البقع". لقد تلقوا إجابتين بناءً على تعريفين مختلفين للعشوائية.
أولاً ، نظروا إلى حقل عشوائي ، حيث يمكن أن يكون كل بلاطة مع احتمال متساوٍ في أي مربع من الحقل. باستخدام هذا التعريف ، وجدوا أنه من أجل إجراء اختيار عشوائي لحقل
n إلى
n ، ستكون هناك حاجة إلى
n 4 حركات (أي 256 خطوة للحقل 4 في 4 و 10 آلاف خطوة للحقل 10 في 10). هذا أكثر مما توقع Diaconis (كما نتذكر ، اقترح
n 3 خطوات).
كان التعريف الثاني لفرصة تشو وهوي أكثر صرامة. لقد اعتبروا حقلًا عشوائيًا ، مع وجود احتمال متساوٍ في أي من التكوينات الممكنة العديدة. لقد أثبتوا أنه ستكون هناك حاجة إلى مزيد من الخطوات لتحقيق هذا التعريف للعشوائية - ليس أكثر من حوالي
n 4 log
n التحركات.
أظهر Chu and Howe أن اختيار لعبة "15" بشكل عشوائي أمر أصعب مما توقع Diaconis ؛ بمعنى ما ، يشير هذا إلى أن الأمر يستغرق وقتًا أكثر مما هو متوقع لإزالة النظام بالكامل في النظام. بفضل عملهم ، أصبحت "العلامة" الآن إحدى مهام التوزيع العشوائي القليلة التي ، وفقًا لما ذكره هاو ، "في الواقع ، يُعرف عدد الخطوات اللازمة لعملية التوزيع العشوائي."
يعمل هاو وبيريز الآن على توسيع الدليل. من بين أمور أخرى ، يهتمون بما إذا كان الحقل يصل إلى حالة عشوائية مع زيادة حجمها من خلال قفزة حادة. لا تبدو الأنظمة ذات هذا السلوك عشوائية على الإطلاق ، وبعد خطوة واحدة فقط تتحول فجأة إلى هذا الحد.
يقول بيريز: "لا نفهم تمامًا أي سلاسل ماركوف تظهر مثل هذا المفاجئ". "هذا هو واحد من أكبر الألغاز في هذا المجال."