الرياضيات في دقيقة: تقليب الفطائر

دعنا نتخيل كومة من الفطائر. في حال لم تكن جيدا في صُنعها، فمن الأرجح أن تكون الفطائر ذات أحجام مختلفة، ما يجعل كومة منها تبدو فوضوية جدا. لذلك فإن ترتيبها حسب الحجم هو من بين الطرق لجعلها تبدو بشكل أفضل، حيث تكون الفطائر الأكبر في القاع والأصغر في القمة.

كيف يمكنك ترتيب الفطائر بهذه الطريقة إذا كانت الآداة الوحيدة التي تملكها هي ملعقة مُسطحة يمكنك استخدامها لقلب الفطائر فقط؟ هناك طريقة واحدة وتتم على النحو الآتي. أولا قُم بترتيب الفطائر حسب الحجم، 1 للأصغر حجما، 2 للأصغر بعدها، وهكذا. ثم اعمل على ايجاد الفطيرة الأولى (قم بالعد من أعلى الكومة) الموجودة في المكان الخطأ (أي، التي تقع تحتها فطائر أصغر حجما). على سبيل المثال، قد تجد الفطيرة رقم 3 في موضع رقم 2. الآن قم بإدخال ملعقتك المسطحة أسفل الفطيرة المخالفة ثم اقلب الكومة بالكامل رأسا على عقِب، الفطيرة المخالفة الآن على القمة. بعد ذلك، أدخِل الملعقة أسفل الموضع الذي من المفترض أن تكون الفطيرة المخالفة فيه (الموضع 3 في مثالنا) ثم اقلب الكومة بالكامل مرة أخرى رأسا على عقب. الفطيرة المخالفة الآن في الموضع الذي من المفترض أن تكون فيه.

إذا واصلت على نفس المنوال، بالنسبة لكل فطيرة مخالفة، ستصل في نهاية المطاف إلى كومة قد تم فرزها حسب الحجم. والذي اتضح أنه إذا كان لديك ما مَجمُوعُهُ n فطيرة ، فإن هذه الطريقة ستتطلب منك 2(n-1) تقليبا كحد أقصى.

من الجيد أن نعرف ذلك، لكنه مازال يعني أننا في حاجة إلى الكثير من التقليب. من أجل كومة من n=10 فطيرة، قد يتطلب منك الأمر 2\times 9 = 18 تقليبا. وهو أمر مضجر وممل. فهل هناك طريقة أفضل؟ إذا كانت الإجابة نعم. فكم عدد التقليبات التي تتطلبها؟

هذا سؤال صعب للغاية. أول تحسين مُعتبر على الحد الأعلى البالغ 2(n-1) تم إثباته من طرف “بيل غيتس”(Bill Gates) مع “كريستوس باباديمتريو” (Christos Papadimitriou) لا غيرهما. عندما كان “غيتس” طالبا في جامعة هارفارد في منتصف السبعينيات 1970. أثبت الإثنان أنه يمكن فرز كل كومة من الفطائر بمقدار (5n+5)/3 تقليب كحد أقصى. لم يتم تحسين هذا الحد حتى عام 2009 من طرف فريق من سبعة باحثين من جامعة تكساس في دالاس، والذي قام بتقسيم المسألة إلى 2220 حالة مختلفة لإظهار أنه يمكن فرز كل كومة بما مقداره 18n/11 تقليب كحد أقصى.

في عام 2011، أظهر فريق آخر من الباحثين أن مسألة العثور على أقصر سلسلة من التقليبات في كومة معينة من الفطائر هي ضمن ما يُدعى NP- الصعبة (NP-hard). أي أن المسألة في الواقع صعبة جدا جدا، للمزيد من التفاصيل راجع الآتي: ما هي مسألتك؟.

مسألة تقليب الفطائر، لا تتعلق بالفطائر فقط، بل بالعثور على التطبيقات في جميع أنواع الحالات التي تتطلب مقاديرها الفرز. راجع هذه المقالة.


المقال الأصلي

Maths in a minute: Flipping pancakes

March 5, 2019

——————

ترجمة: مديحة حوري

math.nights@gmail.com

 

Advertisements
نُشِرت في الرياضيات في دقيقة | الوسوم: , , , , , | أضف تعليق

في البرهان أن n^4 +4^n لا يمكن أن يكون أوليا إلا في حالة واحدة فقط

المسألة

أوجد كل الأعداد الصحيحة الموجبة n حيث n^{4}+4^{n} عدد أولي؟

———–

نُشِرت في في فهم الأعداد الأولية, الأعداد الأولية | الوسوم: , , | أضف تعليق

في البرهان أن n=a^4+4b^4 لا يمكن أن يكون أوليا في حالات معينة

المسألة

a,b عددان طبيعيان. نضع  n=a^{4}+4b^{4}

1/ برهن أنه من أجل b\geq 2 فإن n لا يمكن أن يكون أوليا.
2/ من أجل b=1 هل يمكن أن يكون n أولي؟

——————

نُشِرت في في فهم الأعداد الأولية, في حل مسائل الرياضيات, الأعداد الأولية | الوسوم: , | أضف تعليق

في البرهان أن عددين أوليين فيما بينهما

المسألة

x و y عددين طبيعيين غير معدومين أوليين فيما بينهما. نضع s=x+y و p=xy.

1- برهن أن s أولي مع x وأولي مع y.

2- برهن أن s و p أوليان فيما بينهما.

3- برهن أن s و p من شفعيتين مختلفتين، أحدهما زوجي والآخر فردي.

——————

نُشِرت في في فهم الأعداد الأولية, الأعداد الأولية | الوسوم: | أضف تعليق

برهن أنه ومن أجل بعض الأعداد الصحيحة فإن a=1

المسألة

ليكن a,b,c,d أعدادً صحيحة فردية حيث 0< a < b < c < d و ad=bc. برهن أنه إذا كان a+d=2^{k} و b+c=2^{m} من أجل بعض الأعداد الصحيحة k, m فإن a=1

——————

نُشِرت في في حل مسائل الرياضيات, نظرية الأعداد, القسمة | الوسوم: , | أضف تعليق

برهن أن للمنظومة حل على الأقل في مجموعة الأعداد الصحيحة غير السالبة

مسألة

برهن أنه ومن أجل كل الأعداد الصحيحة غير السالبة a,b,c,d حيث a,b أوليان فيما بينهما. المنظومة:

ax-yz-c=0
bx-yt+d=0

لها حل على الأقل في مجموعة الأعداد الصحيحة غير السالبة.

الحل

————

 

 

نُشِرت في في فهم الأعداد الأولية, الأعداد الأولية | الوسوم: , , | أضف تعليق

Prove: a^{2}+b^{2}=c^{5}+c. has infinitely many relatively prime integer solutions

Problem

Prove that the equation 

a^{2}+b^{2}=c^{5}+c

has infinitely many relatively prime integer solutions.

نُشِرت في في فهم الأعداد الأولية, في حل مسائل الرياضيات, نظرية الأعداد, الأعداد الأولية | الوسوم: , , | أضف تعليق