مهمة منطقية لوضع الدومينو على رقعة الشطرنج. الأولمبياد الرياضي ومشكلات الأولمبياد
أعطيت رقعة شطرنج 8 × 8 ، تم قطع زاويتين متعاكستين قطريًا ، و 31 دومينو ؛ يمكن لكل قطعة دومينو أن تغطي مربعين على السبورة. هل من الممكن رصف اللوح كله بالعظام؟ أعط مبررًا منطقيًا لإجابتك.
المحلول
للوهلة الأولى يبدو أن هذا ممكن. اللوحة 8 × 8 ، إذن ، هناك 64 خلية ، نستثني خليتين ، ما يعني أن 62 باقية ، يبدو أن 31 عظمة يجب أن تناسب ، أليس كذلك؟
عندما نحاول ترتيب قطع الدومينو في الصف الأول ، لدينا 7 مربعات فقط تحت تصرفنا ، وعظمة واحدة تذهب إلى الصف الثاني. ثم نضع قطع الدومينو في الصف الثاني ، ومرة أخرى تنتقل قطعة واحدة إلى الصف الثالث.
سيكون هناك دائمًا عظم واحد في كل صف يجب نقله إلى الصف التالي ، بغض النظر عن عدد المخططات التي نحاولها ، فلن نتمكن أبدًا من وضع جميع العظام.
تنقسم رقعة الشطرنج إلى 32 خلية سوداء و 32 خلية بيضاء. عن طريق إزالة الزوايا المقابلة (لاحظ أن هذه الخلايا لها نفس اللون) ، يتبقى لدينا 30 خلية من لون واحد و 32 خلية من لون آخر. افترض أن لدينا الآن 30 مربعًا أسود و 32 مربعًا أبيض.
كل نرد نضعه على السبورة سيحتل خلية واحدة سوداء وأخرى بيضاء. لذلك ، سيشغل 31 دومينو 31 خلية بيضاء و 31 خلية سوداء. ولكن لا يوجد سوى 30 خلية سوداء و 32 خلية بيضاء على لوحتنا. لذلك ، من المستحيل تحلل العظام.
التحليل مأخوذ من ترجمة كتاب جي لوكمان ماكدويل وهو مخصص للأغراض الإعلامية فقط.
إذا أعجبك الكتاب ، نوصيك بشراء الكتاب.
6. يوجد 235 تطابق في المربع. لاعبان يأخذانهم بدورهم. في خطوة واحدة ، يمكنك أن تأخذ من 1 إلى 6 مباريات. يفوز اللاعب
أخذ المباراة الأخيرة. من يفوز عندما يلعب بشكل صحيح؟
62
7. يتم قطع مربع الزاوية من لوحة 8 × 8. هل من الممكن وضع اللوح في مستطيلات 1 × 3؟
8. من أصل 30 مباراة ، يأخذ لاعبان حسب تقديرهما من 1
ما يصل إلى 6 مباريات. الشخص الذي يأخذ آخر مباراة يفوز.
9. هناك ثلاثة أكوام من الحجارة. الدولة هي ثلاثة أرقام
(x
1
، س
2
، س
3
) ، حيث x i
- عدد الحجارة في الكومة الأولى. الحركة هي عملية النقل من الكومة إلى كومة عدد الأحجار التي تساوي عدد الأحجار في الكومة حيث يتم إجراء النقل. من الحالة الأولية (11 ، 7 ، 6) احصل على الحالة (8 ، 8 ، 8).
10. قسّم الدائرة إلى أقصى عدد من الأجزاء باستخدام أربعة خطوط مستقيمة.
11. قطع الصليب اليوناني بخطين مستقيمين بحيث
لتشكيل مستطيل من الأجزاء الناتجة ، جانب واحد منه ضعف الآخر.
12. يوجد إمدادات 12 لترًا من السوائل والأوعية الفارغة في 9
و 5 لتر. مطلوب قياس 6 لترات بالضبط. كم لتر يمكن قياسه بهذه الأوعية من احتياطي 12 لترًا؟
13. تحديد عدد التسلسلات ذات الطول n من (0 ، 1 ، 2) ،
التي لا توجد فيها وحدتان متتاليتان.
14. هل من الممكن تغطية مربع 10 × 10 بأشكال من النموذج
15. هل من الممكن تغطية مربع 10 × 10 بأشكال النموذج
63
16. هل من الممكن تغطية مربع 8 × 8 بخلية زاوية مقطوعة بأشكال من النموذج
17. هل يمكن تغطيتها بأشكال على شكل رقعة شطرنج 8 × 8 مقطوعة بمربع:
18. هل يمكن وضع رقعة شطرنج بقفص زاوية منحوت بقطع من الشكل
19. هل من الممكن عبور أربعة أزواج من الفرسان بمساعدة قارب من رجلين ، إذا لم يكن من الممكن أن يكون المربع على نفس الشاطئ مع فارس (فرسان) شخص آخر في حالة عدم وجود سيده؟
20. تطوير خوارزمية لإيجاد أصغر رقمين في تسلسل غير مرتب لعدد n.
21. من بين 27 مباراة ملقاة على الطاولة ، يلعب لاعبان بالتناوب مباراة واحدة على الأقل وليس أكثر من أربع مباريات. الفائز هو الشخص الذي سيحصل في نهاية اللعبة على عدد زوجي من المباريات. قم بتطوير خوارزمية للعبة اللاعب الأول.
64
22. يتناوب اثنان من المشاركين في اللعبة في الاتصال برقم من 1 إلى 10.
عند استدعاء رقم ، يضيفه اللاعب إلى مجموع الأرقام الموجود بالفعل (استدعاء الرقم الأول ، ويضيفه اللاعب إلى الصفر). اللاعب الذي يسجل 100 يفوز.
قم بتطوير خوارزمية للعبة اللاعب الأول.
23. ابحث عن الحد الأدنى من عدد الأسئلة (الإجابات الممكنة:
"نعم" ، "لا") رقم مخفي مكون من 5 أرقام ، إذا كان مجموع الأرقام الثلاثة الأولى هو 17.
24. ابحث عن الحد الأدنى من عدد الأسئلة (الإجابات الممكنة:
"نعم" ، "لا") رقم مخفي مكون من 4 أرقام ، إذا كان مجموع الرقمين الثاني والرابع هو 7.
25. ما هو عدد طرق تبادل 100 روبل؟ عملات معدنية في
5 و 10 و 20 و 50 روبل؟
26. احسب بشكل تعاودي عدد الأرقام المكونة من ستة أرقام ومجموع أول أربعة أرقام هو 26 ومجموع آخر رقمين هو 14.
27. احسب بشكل متكرر عدد أقسام الرقم 37 بخمسة فترات ، أولها لا يتجاوز 7 ، والثاني
- 5 ، والثالث والرابع يأخذان القيم من المجموعة
{5, 6, 7, 8}.
28. احسب بشكل تعاودي عدد الأعداد المكونة من سبعة أرقام ومجموع الأرقام الأربعة الأولى هو 21 ، ومجموع الخمسة الأخيرة هو 19.
29. احسب بشكل متكرر عدد أقسام الرقم 27 بأربعة فترات ، أولها لا يتجاوز 7 ،
الثاني هو 8 ، والثالث والرابع يأخذان القيم من المجموعة (3 ، 5 ، 7).
30. احسب بشكل متكرر عدد الأعداد المكونة من خمسة أرقام والتي تضيف أرقامها الثلاثة الأولى ما يصل إلى 21 وتضيف الأرقام الثلاثة الأخيرة ما يصل إلى 12.
65
31. احسب بشكل تعاودي عدد الأعداد المكونة من سبعة أرقام حيث يكون مجموع الخانة الأولى والثالثة 12 ، ومجموع الخمسة المتبقية هو 19.
32. احسب بشكل متكرر
(2 ن - 2) (2 ن - 4) ×. . . × 2
(ن + 1) (ن + 3) ×. . . × (ن + 2 ن - 1)
أ ن − 5
ب
- (ن + 3)
33. احسب بشكل تعاودي عدد الأعداد المكونة من سبعة أرقام والتي يكون مجموع الأرقام الأربعة الأولى فيها 17 ومجموع الثلاثة الأخيرة هو 16.
34. احسب بشكل متكرر عدد أقسام الرقم 17 بأربعة فصول ، الأول منها لا يتجاوز 4 ، والثاني - 8 ، والثالث والرابع يأخذان القيم (3 ، 4 ، 8).
35. احسب بشكل تعاودي عدد الأعداد المكونة من سبعة أرقام والتي يكون مجموع مربعات الأرقام الأربعة الأولى فيها 17 ، ومجموع مربعات الرقمين الأخيرين هو 16.
36. احسب بشكل متكرر عدد أقسام الرقم 25 بأربعة فصول ، أولها لا يتجاوز 8 ،
الثانية هي 3 ، والثالث والرابع يأخذان القيم من المجموعة (2 ، 5 ، 9).
37. احسب بشكل متكرر عدد مواضع الرخ N على السبورة
N × N بحيث تكون الغربان متناظرة فيما يتعلق بكل من الأقطار ولا تهاجم بعضها البعض.
38. احسب بشكل تعاودي عدد المتتاليات الثنائية لـ n من العناصر التي ينقص فيها عنصران متجاوران.
39. نظرا لشبكة N × M:
66
م
ن
أ
ب
احسب بشكل متكرر عدد المسارات من A إلى B. المسار هو سلسلة من الحركات على طول الشبكة التي تقود من اليسار إلى اليمين ومن الأسفل إلى الأعلى.
40. الأعداد معطاة
1
و. . . ، أ ن
بترتيب معين. لحساب المنتج أ
1
·. . . أ
مع الحفاظ على ترتيب العوامل ، هناك العديد من الطرق لوضع الأقواس بين العوامل. احسب عددًا متكررًا من الطرق لوضع الأقواس.
41. احسب بشكل تعاودي عدد الأرقام المكونة من 8 أرقام والتي يكون مجموع الأرقام الخمسة الأولى فيها 29 ومجموع الأرقام الثلاثة الأخيرة هو 21.
67
3
. طرق تحليل الخوارزمية
3.1. فئات الخوارزمية
في الأقسام السابقة ، درسنا الأساليب المختلفة التي يمكن استخدامها في بناء الخوارزميات. لإيجاد حل ، لتحليل فعالية هذا الحل ، يمكن للمرء طرح افتراضات مختلفة ، واستخدام خوارزميات أخرى معروفة بالفعل ، وإعادة صياغة حالة المشكلة ، وما إلى ذلك. يمكنك البحث عن بعض المشكلات المشابهة باستخدام حل معروف واستخدام هذا الحل لإيجاد خوارزمية للمشكلة المطلوبة.
ومع ذلك ، هناك الكثير من المشاكل الخاصة التي تم العثور على حلول لها. هناك المزيد من المهام التي لم يتم حلها أو حلها مع بعض القيود والشروط. عند البحث عن مشكلات مماثلة بين مجموعة المشكلات بأكملها ، فإن تقييم الحلول الحالية وفقًا لدرجة "ملاءمتها" يمكن أن يكون مشكلة صعبة وتستغرق وقتًا طويلاً وليست قابلة للحل دائمًا. سيكون من المفيد والإنتاجي محاولة تحديد فئات المشاكل التي توحدها مشكلة مشتركة ، والأساليب والأساليب الشائعة لحلها ، ثم البحث عن الفئة التي يمكن أن تُنسب إليها مشكلتنا الخاصة التي يجب حلها. بالطبع ، لا ينبغي أن يكون هناك عدد كبير جدًا من هذه الفئات ، ولكن من ناحية أخرى ، يجب ألا يكون هناك عدد قليل جدًا منها ، بحيث مهمة جديدةحدد صفك الجديد ، والذي من غير المحتمل أن يتم استخدامه لحل المشكلات الأخرى.
كمثال على مشكلة تنتمي إلى فئة معينة ، ضع في اعتبارك المشكلة المعروفة المتمثلة في تحديد عملة مزيفة.
المهمة 3.1 (مشكلة حول عملة مزيفة). هناك عملات n ،
من بينها قد يكون هناك واحد مزيف. تختلف العملة المزيفة عن الباقي في الوزن ، ولدينا ميزان به فنجان تحت تصرفنا. يشترط تحديد عملة مزيفة لأدنى عدد من الأوزان أو لتحديد ،
عدم وجود عملات مزيفة.
68
المحلول. تم حل مشكلة العملة المزيفة في Sec. 2.2 ،
ولكن بعد ذلك عُرف أن العملة المزيفة أخف وزنًا بالضرورة. لنحاول الآن حل هذه المشكلة لحالة أكثر عمومية. أي حل لهذه المشكلة (ليس بالضرورة الحل الأمثل)
يمكن تفسيرها على أنها سلسلة من الأوزان. ومع ذلك ، من الواضح أن اختيار العملات المعدنية للوزن في أي خطوة يعتمد على العملات التي تم استخدامها ونتائج الوزن في الخطوات السابقة. سوف نصور تسلسل الأوزان على النحو التالي. نعيد ترقيم العملات ونعرفها على أنها مجموعة S = (1 ، 2 ،. ،. ، ن). يمكن الإشارة إلى مجموعات عدد العملات التي تم وزنها على المقالي اليمنى واليسرى من الميزان بواسطة S
إل
و S.
ص
على التوالى. من الواضح أن الترجيح يكون منطقيًا فقط إذا كانت العناصر الأساسية للمجموعات S.
إل
و S.
ص
مباراة ، أي كل مقياس له نفس عدد العملات. الوزن سيشار إليه بعلامة ":" ثم كل وزن
(س
إل
) : (س
ص
) هناك ثلاث نتائج محتملة. الكثير من العملات
س
إل
قد تكون أخف أو أثقل أو بنفس وزن المجموعة S.
ص
. ثم سنشير إلى نتائج الترجيح هذه على أنها
"" أو "=" على التوالي. يظهر مثال على أوزان أربع عملات معدنية في الشكل. 3.1. تمثل الأشكال البيضاوية الأوزان ، وتمثل المربعات النتائج ، مما يشير إلى رقم العملة المزيفة وما إذا كانت أخف أو أثقل من غيرها.
يشار إلى حالة عدم وجود عملة مزيفة بالرقم "0" ، وتتوافق المربعات المشطوبة مع الحالات التي لا يمكن حدوثها.
سنقدر الحد الأقصى لعدد الأوزان المطلوبة لحل المشكلة ، أي الحالة الأسوأ. كما يظهر في الشكل. 3.1 ، يتم حل المشكلة في 3 أوزان في أسوأ الحالات. لاحظ أنه حتى في أفضل الأحوال نحتاج إلى 2 على الأقل
وزن. هل يمكن تحقيق نتيجة أفضل؟
على التين. يقدم الشكل 3.1 حلاً آخر لمشكلة وزن أربع عملات. في الخطوة الأولى ، لا نزن زوجًا من العملات المعدنية ، بل نزن جميع العملات ، ونقسمها إلى مجموعتين. نتيجة لذلك ، حققنا أنه في أحسن الأحوال لا يلزم سوى وزن واحد ،
ومع ذلك ، في أسوأ الحالات ، يكون عدد الأوزان مرة أخرى 3.
69
(1) : (2)
(1) : (3)
(1) : (4)
0 4 ت
4 لتر
3 ت
3 لتر
(1) : (4)
2 ت
1 لتر
(1) : (4)
2 لتر
1 ت
=
=
=
>
>
>
>
>
=
=
أرز. 3.1. حل مشكلة العملة المزيفة
لاحظ أنه على عكس خيار الوزن الأول ،
هو مبين في الشكل. 3.1 ، في الإصدار الثاني ، لم نقم بتعريف مخطط الوزن فحسب ، بل قدمنا أيضًا مفهومًا جديدًا لعملات مزيفة مرشحة. في الواقع ، تأمل نتيجة الوزن الأول (1 ، 2): (3 ، 4). دع (1 ، 2) ل
= (1 ، 2) ، و S.
ص
= (3 ، 4). ثم
س
إل
ص
. من هذه النتيجة لا يمكن الحكم على ما إذا كانت العملة المزيفة أخف أو أثقل من جميع العملات الأخرى ،
وفي أي مجموعة هو. ومع ذلك ، يمكن افتراض ذلك
(وبشكل أكثر دقة - يمكن القول) أنه إذا كانت العملة المزيفة تنتمي إلى المجموعة S.
إل
، فإن العملة المزيفة أخف من العملات الأخرى ، ونشير إلى هذه المجموعة بالحرف L. في حالتنا ، إذا كانت العملات المعدنية ذات الأرقام 1 أو 2 مزيفة ، فهي أخف من العملات الحقيقية. إذا كانت العملات المزيفة بأرقام 3 أو
4 ، ثم تكون أثقل من تلك الحقيقية ، سنشير إلى المجموعة المقابلة بالحرف T. في الشكل. 3.2 يُشار إلى المنتجات المقلدة الخفيفة والثقيلة بعلامات على حواف الشجرة.
من الواضح أنه يمكن للمرء أن يجيب على السؤال حول العدد الأمثل للأوزان من خلال الاستمرار في فرز المخططات الممكنة لاختيار العملات المعدنية. نظرًا لأن عدد العملات محدود ، يمكن إكمال هذا التعداد عاجلاً أم آجلاً. في الوقت الحالي ، دعنا نتناول الحلين اللذين تم الحصول عليهما ونحاول تحليل ما قدموه
70
(1.2) لتر
(3.4) ت
(1.2) ت
(3.4) ل
(1,2) : (3,4)
(3) : (4)
4 ت
3 ت
(1) : (2)
1 لتر
=
=
>
>
>
=
0 2 لتر
(3) : (4)
3 لتر
4 لتر
(1) : (2)
2 ت
=
>
>
=
1 ت
أرز. 3.2 حل آخر لمشكلة العملة المزيفة لنا من وجهة نظر نهج عام لحل المشكلة.
كما هو معروف ، يمكن وصف أي استراتيجية لوزن العملة باستخدام شجرة ثلاثية أو ثلاثية. بمعنى آخر ، المشكلة قيد النظر تنتمي إلى فئة المشاكل ،
وصفتها الأشجار الثلاثية. يجعل هذا التصنيف للمشكلة من الممكن تحليل ليس كل حل محدد ، ولكن جميع الحلول بشكل عام ، بناءً على الخصائص المعروفة للأشجار.
وهكذا ، انتهى التكرار الطرق الممكنةالترجيح هو في الواقع بحث من خلال مختلف الأشجار الثلاثية ، والتي ، بالطبع ، هناك الكثير منها بشكل كبير. من ناحية أخرى ، دعنا نحاول تحديد ما يمكن تحقيقه بشكل عام عند حل مشكلة معينة ، باستخدام الانتماء إلى هذه الفئة المعينة.
من التين. 3.1 و 3.2 ، يمكن ملاحظة أنه عند تصوير تسلسل الأوزان باستخدام شجرة ، فإننا ننسب كل وزن إلى رأس شجرة ليس ورقة (تم تصويره باستخدام أشكال بيضاوية) ، بينما النتائج ، بما في ذلك النتائج المستحيلة ،
تتوافق مع أوراق الشجرة (الموضحة بالمربعات). يمكن ترتيب جميع عقد الشجرة حسب المستويات ،
71
في
أ
=
=
>
في
أ
و
و
و
=
>
في
أ
و
و
و
=
>
في
أ
و
و
و
=
>
في
أ
و
و
و
=
>
في
أ
=
>
في
أ
=
>
في
أ
>
إلى
في
إل
في
0
في
1
في
ل
-
1
في
ل
……
………………
………
…
…
……
…
…
…
…
…
……
……
…
…
جي
أ =
ل
أرز.
3.3.
تي
شجرة الوزن الربيعي
72
أولئك. ببُعدهم عن جذر الشجرة. رقم المستوى يساوي عدد الحواف التي يجب أن تمر من الجذر للوصول إلى الرأس. مستوى معين(الشكل 3.3). إذا كان عمق الشجرة هو مستوى الورقة الأبعد عن الجذر ، فإن هذه القيمة تساوي عدد الأوزان في أسوأ الحالات.
كم عدد النتائج المحتملة في مشكلتنا؟ قد يتضح أن كل عملة من العملات المعدنية n عبارة عن عملة خفيفة مزيفة أو عملة ثقيلة مزيفة ، وقد لا يكون هناك أي عملات معدنية مزيفة على الإطلاق.
وبالتالي ، لدينا نتيجة 2n + 1. هذا يعني أن في الشجرة
المطابق لمخطط الوزن ، يجب أن يكون على الأقل
2n + 1 ورقة. شجرة ثلاثية العمق تحتوي على الأكثر ،
من 3
أوراق. من هذا يمكننا تقدير أدنى عمق ممكن للشجرة
3
ل
≥ 2n + 1 ،
وبالتالي
ل ≥ السجل
3
(2 ن + 1).
(3.1)
وبالتالي ، بالنسبة إلى n = 4 ، يكون الحد الأدنى لعدد الأوزان الممكنة أكبر من أو يساوي 2. هنا لا نعني الحد الأدنى لعدد الأوزان لهذا المخطط - كما في الشكل. 3.2 ، وهناك حالات يكون فيها حل المشكلة موجودًا بالفعل بعد الوزن الأول - نقوم بتقييم الخيار الأسوأ ، أي الحد الأقصى لعدد الأوزان لنظام معين ، وبعبارة أخرى ، نحن نبحث عن الحد الأدنى من بين الأعماق القصوى لجميع الأشجار ذات الأوراق 2n + 1 على الأقل.
ومع ذلك ، يمكن إثبات أنه لا توجد طريقة ترجيح تعطي المساواة في التقدير (3.1).
نظرية 3.1
يتم تقدير عدد الأوزان في أسوأ حالة لمشكلة العملة المزيفة على أنها l> log
3
(2 ن + 1).
دليل - إثبات. كما ذكرنا سابقًا ، بالنسبة لـ n من العملات المعدنية ، هناك 2n + 1 من النتائج المحتملة. يمكن أن يكون لكل وزن ثلاث نتائج محتملة ، ولكل نتيجة نتائجها الخاصة
73
مخطط مزيد من الأوزان. في الوقت نفسه ، يكون للمخطط عدد خاص به من النتائج المحتملة ، مع مراعاة نتيجة الوزن الأخير. دعه يزن | S.
إل
| = | S.
ص
| = ك ، أي
تُستخدم العملات المعدنية k في المقياس والعملات المعدنية k على الأخرى ،
أين ك ≤ ن / 2. إذا كان في نفس الوقت S.
إل
ص
، ثم عملات معدنية من S.
إل
نعلن عن مرشحين للعملات المعدنية المزيفة الخفيفة والعملات المعدنية من S.
ص
- المرشحون للعملات الثقيلة المزورة. في هذا الطريق،
مع نتيجة الوزن الأول ، يمكن الحصول على نتيجة 2k.
وبالمثل ، بالنسبة لـ S.
إل
> S.
ص
2k نتيجة أخرى ممكنة. لذلك ، بالنسبة لـ S.
إل
= S.
ص
النتائج المتبقية 2n + 1 - 4k ممكنة.
إذا ثبتت المساواة في (3.1) ، فهذا يعني أن الشجرة الثلاثية كاملة وجميع أوراقها في المستوى التاسع.
ولكن لهذا من الضروري بعد كل وزن أن يتم توزيع النتائج المحتملة بالتساوي على الفروع الثلاثة والمساواة
2 كيلو = 2 ن + 1 - 4 كيلو ،
وهو مستحيل لأن 2k دائمًا عدد زوجي و
2n + 1 - 4k دائمًا أمر غريب.
تم استخدام فكرة مهمة في إثبات النظرية 3.1:
لكي تكون شجرة الترجيح مثالية ، أو على الأقل قريبة من المستوى الأمثل قدر الإمكان ، من الضروري أن يتم توزيع النتائج بالتساوي على جميع نتائج كل وزن.
وبالتالي ، حصلنا على تقدير لأسوأ عدد من عمليات الوزن في مشكلة العملة المزيفة من خلال ربط هذه المشكلة بفئة المشكلات.
وصفتها الأشجار الثلاثية. فكر الآن في مشكلة معدلة قليلاً.
المشكلة 3.2 (مشكلة حول عملة مزيفة في وجود معيار). هناك عدد n من العملات ، قد يكون من بينها عملة مزيفة ، وعملة أخرى ، من المعروف على وجه اليقين أنها حقيقية. يلزم تحديد العملة المزيفة بأقل عدد من الأوزان أو إثبات عدم وجود عملات مزيفة.
74
المحلول. تختلف هذه المشكلة عن المشكلة السابقة من خلال وجود عملة مرجعية إضافية ، ولكن اتضح أن هذه العملة الإضافية تسمح للشخص ببناء أشجار الوزن المثلى التي يتم تحقيق المساواة في (3.1). تدل عليه ن ل
العدد الذي يتم من أجله المساواة
3
ل
= 2 ن ل
+ 1.
(3.2)
عند النظر في المشكلة السابقة في النظرية 3.1 ، حصلنا على: لتحقيق المساواة (3.1) ، يجب أن تكون شجرة الترجيح كاملة. لذلك ، إذا كان من الممكن بناء مثل هذه الشجرة المثلى من المستويات l ، فسوف تحدد مخططًا لأوزان l لـ n l
عملات معدنية. لاحظ أن العلاقة التالية صحيحة:
nl
= 3nl − 1
+ 1.
(3.3)
منذ ل n
0
= 0 في (3.2) نحصل على المساواة ، 3 0
= 2 0 + 1 ،
ثم من هنا باستخدام (3.3) يمكننا الحصول على n
1
= 1 ، ن
2
=
4 ، ن
3
= 13 وما إلى ذلك. الحل (3.2) هو التسلسل
0, 1, 4, 13, 40, . . ..
وهكذا ، عندما تثبت المساواة (3.2) ، فإن مجموعة n
l تنقسم العملات المعدنية إلى ثلاثة أجزاء متساوية بواسطة n l − 1
العملات المعدنية ولا تزال هناك عملة واحدة متبقية. دعونا نفكر في المواقف المختلفة التي قد تنشأ أثناء عملية الوزن.
المخطط 1. دعنا نحصل على n i في بداية قياس الوزن
العملات المعدنية ، حيث n أنا
ينتمي إلى التسلسل (3.3) بالنسبة للبعض أنا. لنضع n i − 1
عملات معدنية ، حيث ن
أنا
= 3n أنا − 1
+ 1,
ثم نضيف عملة مرجعية إلى المقلاة اليسرى للميزان ، وواحدة من العملات المتبقية n i − 1
+ 1 عملات معدنية. قم بالإشارة إلى المجموعات الموزونة ، كما كان من قبل ، بواسطة S.
إل
و S.
ص
الآن دع نتيجة لوزن S.
إل
= S.
ص
. نظرًا لأن العملة المرجعية شاركت في الوزن ، فمن الواضح أن العملة المزيفة ، إن وجدت ، من بين العملات غير المستخدمة.
أنا − 1
العملات المعدنية ، ويتم تقليل المشكلة إلى مشكلة في n i − 1
عملات معدنية. حيث
75
نتيجة الترجيح ، لا يزال لدينا 2n أنا − 1 ممكن
+ 1 =
3
أنا − 1
النتائج. دعنا الآن
إل
ص
. هذا يعني أن العملة المزيفة إما في المجموعة S.
إل
وفي نفس الوقت يكون أخف من الآخرين ، أو في المجموعة S.
ص
وبعد ذلك يكون أثقل من الآخرين.
علاوة على ذلك ، هناك n أنا − 1
العملات الخفيفة المشبوهة و n i − 1
+ 1 ثقيل مشبوه وهذا معًا يعطي 2n i − 1
+ 1 = 3
أنا − 1
النتائج الممكنة.
أخيرًا ، دع S.
إل
> S.
ص
. ثم لدينا n أنا − 1
المرشحين للعملة الثقيلة و n أنا − 1
+1 مرشح للرئتين ومجموع 2n أنا − 1
+1 =
3
أنا − 1
النتائج. لذلك ، باستخدام مخطط الوزن الأول ، نحصل على 3
تم توزيع النتائج الأولية بالتساوي وفقًا لنتائج الوزن. لتحديد ما إذا كان من الممكن تعيين مخطط الوزن بحيث يتم تقسيم النتائج بعد كل وزن إلى عدد متساوٍ من الأجزاء ، ضع في اعتبارك نتائج الوزن. من الواضح ، بالنسبة لـ S.
إل
= S.
ص
نصل إلى نفس المشكلة ، فقط بأبعاد أصغر ، ويمكننا دائمًا إجراء الترجيح وفقًا للمخطط 1 مرة أخرى ، ولكن بقيمة أصغر لـ i.
مخطط 2. دعونا الآن S
إل
ص
. في هذه الحالة ، نحدد استراتيجية الترجيح على النحو التالي. البيانات الأولية هي أنه في مرحلة ما من سلسلة الترجيحات لدينا 3
أنا
= 2n أنا
+ 1 عملات معدنية ، من بينها n i
المرشحين المزيفين الخفيفين و n i
+ 1 مرشحين للثقل ، في حين أن الرقم n أنا
هو رقم من النموذج (3.3)
ن أنا
= 3n أنا − 1
+ 1.
ضع على كل مقلاة مقياس n i − 1
المرشحين السهل و n
أنا − 1
+1 ثقيل. نظرًا لوجود 2n أنا فقط
+1 = 2 (3n أنا − 1
+1) +1 = 6n أنا − 1
+3
العملات المعدنية ، وتزن
2n أنا − 1
+ 2n أنا − 1
+ 2 = 4n أنا − 1
+ 2
العملات المعدنية ، فلا يزال هناك 2n أنا − 1
+ 1 عملات معدنية ، من بينها n i − 1
+ 1
الرئتين و n أنا − 1
ثقيل. نظرًا لوجود نفس العدد من العملات الخفيفة والثقيلة على كلا المقياسين ، فعندئذٍ إذا كانت المقاييس غير متوازنة ،
هذا يعطينا n i − 1
المرشحين للعملات الخفيفة (من الوعاء الذي تبين أنه أخف) و n i − 1
+ 1 مرشح للثقل (من الوعاء الذي تبين أنه
76
أثقل). هذا يقودنا إلى البيانات الأصلية لنفس المخطط
(المخططات 2) ، ولكن من أجل 3
أنا − 1
= 2n أنا − 1
+ 1 عملات معدنية. إذا كانت الموازين متوازنة ، فهذا يعني أنه يجب علينا البحث عن عملة مزيفة بين n i 1
+ 1 الرئتين و n أنا − 1
العملات الثقيلة ، والتي تتوافق مع المخطط 3. من الواضح ، 2n i − 1
نتائج +1 ، أي مرة أخرى ، يتم تقسيم مجموعة جميع النتائج الممكنة إلى ثلاثة أجزاء متساوية.
مخطط 3. دعونا الآن S
إل
> S.
ص
. في هذه الحالة لدينا 3
أنا
=
2n أنا
+ 1 عملات معدنية ، من بينها n i
+ 1 مرشح مزيف خفيف ، و n i
المرشحين الوزن الثقيل. جميع الحجج مشابهة للمخطط 2 ، مع اختلاف أنه عند قياس الوزن ، عليك وضع n i − 1
+ 1 مرشح سهل ، و n i − 1
ثقيل. إذا لم تكن المقاييس متوازنة ، فهذا يعطينا مرة أخرى النمط 3 مقابل 3
أنا − 1
العملات المعدنية ، وإلا نحصل على شروط الوزن المقابلة للمخطط 2. ومرة أخرى ، في جميع الحالات ، يتم تقسيم مجموعة النتائج المحتملة إلى ثلاثة أجزاء متساوية من 2n i − 1
+ 1.
وهكذا ، لدينا ثلاث مرات
1 2
3
=
>
=
=
أرز. 3.4. الانتقالات بين مخططات الترجيح في مشكلة العملة المزيفة للحالة الشخصية الموضحة أعلاه وقاعدة الترجيح لكل ولاية. اعتمادًا على نتيجة الوزن ، ننتقل إلى حالة أخرى (أو نبقى في نفس الحالة) ، ولكن لعدد أقل من العملات المعدنية. في كل وزن ، يتم توزيع عدد النتائج المحتملة بالتساوي وفقًا لنتائج الوزن. يظهر مخطط التحولات بين الدول في الشكل. 3.4. يظهر مثال على أوزان 27 قطعة نقدية في الشكل. 3.5
77
إثبات أن رقعة الداما هي 10Xلا يمكن تقطيع 10 على طول خطوط الشبكة إلى مستطيلات 1X4. (الحلول وفقًا لـ D.Yu. Kuznetsov.)
المحلول 1 . قسّم اللوحة إلى مربعات 2 × 2 وقم بتلوينها بنمط رقعة الشطرنج (الشكل 1). لاحظ أن أي مستطيل 1x4 يحتوي على (2) خلايا سوداء وبيضاء متساوية ، ولكن مع هذا التلوين ، هناك 52 خلية سوداء و 48 خلية بيضاء على اللوحة ، أي ليس بالتساوي. هذا يعني أنه لن يكون من الممكن قطع لوحة 10x10 إلى مستطيلات 1x4.
المحلول 2 . دعونا نلون اللوحة بأربعة ألوان (الشكل 2). لاحظ أن أي مستطيل يحتوي على خلية واحدة من كل لون من الألوان الأربعة ، ولكن مع تلوين معين ، هناك 25 خلية من اللونين الأول والثالث على اللوحة ، و 26 خلية من الخليتين الثانية و 24 خلية من الرابع ، أي ليس بالتساوي. هذا يعني أنه لن يكون من الممكن قطع لوحة 10x10 إلى مستطيلات 1x4.
1. اقطع خلايا الزاوية اليمنى واليسرى السفلية من رقعة الشطرنج. هل من الممكن تقطيع الشكل الناتج إلى قطع دومينو 1 × 2؟ وإذا قمت بقص أسفل اليمين وأعلى اليسار؟
2. هل من الممكن قطع لوح 6x6 إلى دومينو بحيث يكون هناك 11 لوحًا أفقيًا بينهم بالضبط؟ (تلوين أفقي بلونين.)
3. قم بتلوين الرسم بأربعة ألوان بحيث يتم طلاء الأجزاء المجاورة بألوان مختلفة. هل من الممكن الحصول على ثلاثة ألوان؟ (انظر النشاط 6: التلوين الخريطة الجغرافية- فئة 5-6).
4. في مربع 4x4 ، خلايا النصف الأيسر مطلية باللون الأسود والباقي باللون الأبيض. في عملية واحدة ، يُسمح بإعادة تلوين جميع الخلايا الموجودة داخل أي مستطيل باللون المعاكس. كيف تحصل على تلوين الشطرنج من التلوين الأصلي بثلاث عمليات؟
5. يجلس العديد من الجنادب على نفس الخط المستقيم والمسافات بين الجيران متساوية. في كل دقيقة يقفز أحدهم إلى نقطة متناظرة مع جندب آخر. هل يمكن للجندب ساشا أن ينتهي بعد فترة في المكان الذي كان يجلس فيه جاره ليوشا في البداية؟
6. أ) هل يمكن قطع رقعة الشطرنج إلى أشكال تتكون من 4 خلايا على شكل الحرف "T"؟
ب) هل من الممكن قطع رقعة الشطرنج 10x10 إلى مثل هذه الأشكال؟
7. هل من الممكن تقسيم مربع 8x8 بزاوية مقطوعة إلى مستطيلات 1x3؟
8. هل يمكن تقطيع لوح 10x10 إلى قطع من أربع خلايا على شكل الحرف "L"؟ (تلوين أفقي بلونين.)
9. يتم تقطيع اللوح 8x8 إلى قطع دومينو 2x1. هل يمكن أن يكون هناك 15 قطعة دومينو رأسية و 17 أفقية؟
10. ينقسم المثلث إلى مثلثات (25 قطعة) كما هو موضح بالشكل. يمكن للخنفساء أن تمشي في مثلث ، وتتحرك بين مثلثات متجاورة (على الجانب). ما هو الحد الأقصى لعدد المثلثات التي يمكن للخنفساء أن تمر من خلالها إذا لم تزور كل مثلث أكثر من مرة؟
11. ما هو أكبر عدد من المعينات ، كل منها يتكون من مثلثين متساويين الأضلاع مع الضلع 1 ، يمكن قصهما من مثلث متساوي الأضلاع ضلع 5 (انظر شكل المسألة السابقة).
12. القلعة المثلثة مقسمة إلى 100 قاعة مثلثة متطابقة. يوجد باب في منتصف كل جدار. كم عدد الغرف التي يمكن أن يزورها الشخص الذي لا يرغب في زيارة أي مكان أكثر من مرة؟
الفصل 2 رقعة الشطرنج
للحصول على وصف تفصيلي لرياضيات الشطرنج ، والتي نحن على وشك البدء ، فمن الطبيعي أن نبدأ بها مسائل حسابيةحول السبورة نفسها ، دون وضع أي قطع عليها حتى الآن. هذا هو الموضوع الذي خصص هذا الفصل.
دعونا أولا وقبل كل شيء ننظر في العديد من المشاكل المتعلقة بتغطية لوح بـ 2 × 1 دومينو. يفترض في كل مكان أن كل قطعة دومينو تغطي مربعين من اللوحة ، وكل مربع مغطى بنصف قطع الدومينو. لنبدأ بالمشكلة القديمة التالية.
هل من الممكن تغطية مربع بحجم 8 × 8 بدومينو تقطع منه خلايا الزاوية المقابلة (الشكل 2 أ)؟
يمكننا استخدام التفكير الجبري ، لكن حل "الشطرنج" أبسط وأكثر أناقة. دعونا نلون مربعنا المقطوع بالأبيض والأسود ، ونحوله إلى رقعة شطرنج بدون حقلي زاوية a8 و h1 (الشكل 2 ب). لأي غطاء للوحة ، يغطي كل دومينو مربعًا أبيض وآخر أسود. لدينا حقلين أبيض أقل من الأسود (الحقول المقطوعة بيضاء) ، وبالتالي لا توجد التغطية اللازمة! كما نرى ، فإن تلوين اللوحة لا يجعل من السهل على لاعب الشطرنج التنقل أثناء اللعبة فحسب ، بل يعمل أيضًا كوسيلة لحل المشكلات الرياضية.
في المشكلة المدروسة ، كان من المهم ألا يتم قطع حقول الزاوية من اللوحة ، بل أن تكون من نفس اللون. من الواضح أنه بغض النظر عن كيفية قص زوج من الحقول ذات اللون الواحد ، فلن تكون قادرًا على تغطية بقية اللوحة بالدومينو. وهكذا تنشأ المشكلة التالية.
افترض الآن أنه تم قطع حقلين من ألوان مختلفة على رقعة الشطرنج. هل من الممكن دائمًا تغطية باقي اللوح بـ 31 دومينو؟
اتضح أن ذلك دائما. تم العثور على دليل مذهل من قبل عالم الرياضيات الأمريكي الشهير ر.غوموري. دعنا نرسم على رقعة الشطرنج الحدود بين الرأسيات والأفقية كما هو موضح في الشكل. 3. في المتاهة بين هذه الحدود ، تتبع الحقول السوداء والبيضاء بعضها البعض ، بالتناوب مثل الأزرار ذات اللونين على خيط مغلق (المسار الذي يمكن تجاوز هذه المتاهة على طوله مغلق). بغض النظر عن حقلين من ألوان مختلفة قمنا بقطعها من اللوحة ، فإن الخيط سوف ينكسر: في مكان واحد إذا كانت الحقول المقطوعة متجاورة ، وفي مكانين بخلاف ذلك. في هذه الحالة ، ستتألف كل قطعة من الخيط من عدد زوجي من الحقول. وبالتالي ، فإن هذه القطع ، وبالتالي اللوحة بأكملها ، يمكن تغطيتها بالدومينو!
أرز. 3. متاهة جوموري |
سيتم العثور على أفكار غريبة تتعلق بالأزرار والخيوط في الفصل 11.
افترض أن بعض الحقول مقطوعة من رقعة الشطرنج بحيث لا يمكن وضع قطع الدومينو على الجزء المتبقي منها. من السهل التحقق من أن أقل عدد من الحقول المقطوعة بهذه الخاصية هو 32 - هذه كلها حقول من نفس اللون (أبيض أو أسود).
إن مشاكل رقعة الشطرنج والدومينو ليست سوى جزء صغير من سلسلة ضخمة من المشاكل من هذا النوع. ابتكر عالم الرياضيات الأمريكي S.Golomb علمًا كاملاً ، أطلق عليه اسم Polymipo ، وقد تمت ترجمة كتابه حول هذا الموضوع في العديد من دول العالم ، بما في ذلك بلدنا. بشكل عام ، البوليومينو عبارة عن شكل متصل ببساطة يتكون من مربعات. من وجهة نظر لاعب الشطرنج ، يعني كونك متصلًا ببساطة أنه يمكن تجاوز جميع مربعات البوليومينو بحركة الرخ. اعتمادًا على عدد المربعات 07 ، تأتي الأشكال المتعددة الدرجات بدرجات مختلفة. يحتوي المونومينو على مربع واحد ، ودومينو اثنان ، وثلاثة ترومينو ، وأربعة رباعي ، وخماسي خمسة ، وستة مربعات هيبتومينو ، وهكذا. سنناقش المزيد من القضايا المتعلقة بلوحة الشطرنج العادية. من الواضح أنه من المستحيل تغطية dssk مع ترومينو مستقيم فقط ، أي دومينو 3 × 1 ، حيث أن 64 غير قابل للقسمة على 3. تنشأ المشكلة التالية.
هل من الممكن تغطية رقعة الشطرنج بـ 21 ترومينو مستقيمة ومونومينو واحد؟ إذا كان الأمر كذلك ، فما هي الحقول التي يمكن أن يشغلها المونومينو؟
أحد طلاءات dapo الضرورية في الشكل. 4 ا. لتحديد الترتيبات الممكنة للمونومين ، نرسم نظامين من الخطوط المتوازية على السبورة ، كما هو موضح في الشكل. 4 ب.
من السهل أن نرى أنه بالنسبة لأي غطاء ، يغطي كل ترومينو حقلاً واحدًا بالضبط يمر من خلاله الخط الصلب ، وحقلًا يمر خلاله الخط المتقطع بالضبط. نظرًا لأن عدد الحقول التي تتقاطع معها خطوط صلبة هو 22 ، بالإضافة إلى عدد الحقول التي تتقاطع معها خطوط متقطعة ، وهناك 21 ترومينو ، يمكن للمونومينوس أن تغطي فقط الحقول التي تتقاطع مع مجموعتي الأسطر. ولا يوجد سوى أربعة مربعات من هذا القبيل: c3 و c6 و f3 و f6! من خلال تدوير اللوحة 90 و 180 و 270 درجة ، يمكنك الحصول على التغطية المناسبة لكل من هذه الحقول الأربعة.
تختلف المهمة التالية إلى حد ما عن تلك التي تمت مناقشتها أعلاه.
هل من الممكن تغطية رقعة الشطرنج بالدومينو بطريقة تجعل من المستحيل رسم حد واحد بين الأعمدة والأفقية دون عبور الدومينو؟
إذا تخيلنا أن اللوح عبارة عن جدار ، وأن قطع الدومينو عبارة عن طوب ، فإن وجود الحد (التماس) المحدد يشير إلى البناء الهش. بمعنى آخر ، فإن المشكلة تتساءل عما إذا كان من الممكن ترتيب "الطوب" بحيث لا ينهار "الجدار". المستطيل الذي يمكن تغطيته بالطريقة المطلوبة يسمى "قوي". يمكن رؤية "قوة" رقعة الشطرنج في الشكل. 5. في الحالة العامة ، يوضح Gardner أنه يمكن طي الدومينو في مستطيل "قوي" إذا كانت مساحته متساوية ، وكان طوله وعرضه أكبر من أربعة ، مع الاستثناء الوحيد هو مربع 6 × 6.
أدناه سنتعامل غالبًا مع ألواح الشطرنج المستطيلة بحجم أو بآخر. في هذه الحالة ، يُفترض دائمًا أن لوحة m × n بها أعمدة m و n أفقية (شطرنج). نقول أن اللوحة تكون "زوجية" إذا كان عدد حقولها زوجيًا ، و "فردي" بخلاف ذلك. أينما لم يتم تحديد أبعاد اللوحة ، فإننا نعني رقعة الشطرنج القياسية التي م = ن = 8.
اللوحة 100x4 مغطاة بالدومينو. أثبت أنه يمكن قطعه على طول أحد الحدود بين الرأسي والأفقي دون التأثير على أي من قطع الدومينو.
أي من الحدود المحددة يقسم اللوحة إلى جزأين ، يتألفان من عدد زوجي من الحقول. نقسم حقول كل جزء إلى فئتين: قطع الدومينو المغطاة بالكامل في هذا الجزء ، وقطع الدومينو المغطاة التي تتقاطع مع الحدود. نظرًا لأن عدد الحقول لكل جزء هو زوجي (ربما صفر) ، بالإضافة إلى عدد حقول الفئة الأولى (كل دومينو يغطي حقلين) ، فإن عدد حقول الفئة الثانية يكون زوجيًا. وهذا يعني أن عدد قطع الدومينو التي تعبرها الحدود هو عدد زوجي. يوجد إجمالي 102 حدود فاصلة (99 عموديًا و 3 أفقيًا) ، وإذا تقاطع كل منها مع قطع الدومينو ، فعندئذٍ يشارك في التغطية ما لا يقل عن 102 × 2 = 204 قطعة دومينو. لدينا 200 منهم فقط! في الواقع ، لقد أظهرنا أن المستطيل 100x4 "ضعيف".
يتم حل مسألة إمكانية تغطية لوحة مستطيلة عشوائية باستخدام k-minos الخطي (الدومينو k × 1) من خلال النظرية التالية.
يمكن تغطية لوحة m × n بـ k-minos الخطي إذا وفقط إذا كان واحدًا على الأقل من الأرقام m أو n قابلاً للقسمة على k بدون باقي.
نوضح النظرية بالمثال التالي.
هل من الممكن تغطية لوحة 10x10 (يتم لعب مائة قطعة مربعة على مثل هذه اللوحة) بأشكال رباعية مستقيمة؟
رباعي التترامينو المستقيم له أبعاد 4 × 1 ، مما يعني أنه من حيث المبدأ يمكن أن تغطي 25 قطعة جميع حقول اللوح. ومع ذلك ، فإنه يترتب على النظرية أن هذا مستحيل - 10 لا يقبل القسمة على 4.
دعونا نفكر في بعض المشاكل الأخرى حول رقعة الشطرنج. في حل المشكلة التالية ، يتم استخدام تلوينه.
دع اللوحة تتكون من عدد فردي من الحقول. سنضع بعضًا في كل مجال من مجالاته قطعة شطرنج. هل من الممكن نقل كل هذه القطع إلى المربعات المجاورة (رأسيًا أو أفقيًا) بحيث لا ينتهي اثنان منها في نفس المربع؟
المهمة مستحيلة. في الواقع ، إذا كانت الإزاحة المشار إليها موجودة ، فإن كل قطعة "بيضاء" (تقف على حقل أبيض) ستصبح "سوداء" (تقع على حقل أسود) ، وكل "سوداء" - "بيضاء".
وبالتالي ، فإن اللوحة ستتألف من نفس العدد من الحقول البيضاء والسوداء ، وهذا يتعارض مع "شذوذتها".
شعبية هي مشاكل قطع رقعة الشطرنج. وأشهرها ما يلي ، التي يملكها S. Loyd.
يوجد أربعة فرسان في الحقول a1 و b2 و c3 و d4. قم بتقطيع اللوحة إلى أربعة أجزاء متطابقة (تتزامن عند تركيبها) بحيث يكون لكل منها حصان.
في مشاكل القطع ، يُفترض دائمًا أن التخفيضات تتم فقط على طول الحدود بين الخطوط الرأسية والأفقية للوحة. يظهر حل هذه المشكلة في الشكل. 6. منذ زمن لويد ، ظهرت العديد من المشاكل الجديدة والأكثر صعوبة حول هذا الموضوع. على وجه الخصوص ، تم حل مشاكل قطع السبورة إلى أربعة أجزاء متطابقة لمواضع مختلفة من الفرسان (يلعب الفرسان ، بالطبع ، دورًا رمزيًا فقط). لا يزال هناك العديد من القضايا التي لم يتم حلها بشأن هذه المسألة. على سبيل المثال ، لا يزال عدد الطرق التي يمكن بها تقطيع اللوحة العادية (بدون قطع) إلى قطعتين متطابقتين غير معروف.
أرز. 6. مشكلة خيول لويد الأربعة |
دع ، بعد عدة قطع للوحة ، يُسمح بتحويل الأجزاء الناتجة بحيث لا يمكن للقطع التالي قطع جزء واحد ، بل عدة أجزاء في وقت واحد. كم عدد القطع المطلوبة للحصول على 64 مساحة لوحية فردية (1 × 1 مربعات)؟
أولاً ، نقطع اللوح إلى نصفين ، ثم نضع كلا النصفين جنبًا إلى جنب ونقطع اللوحة إلى أربعة أجزاء متطابقة ، إلخ. في المجموع ، ستكون هناك حاجة إلى 6 قطع (2 e \ u003d 64) ولا يمكن الاستغناء عن رقم أصغر .
دع الآن يُسمح بقطع أجزاء من اللوحة بشكل منفصل فقط. كم عدد القطع المطلوبة للحصول على 64 حقلاً في هذه الحالة؟
كقاعدة عامة ، تسبب هذه المهمة (خاصة إذا تم اقتراحها بعد المهمة السابقة) بعض الصعوبات. يبدو أن هذا يرجع إلى بعض الجمود في تفكيرنا. بعد كل شيء ، من الواضح على الفور أن هناك حاجة إلى 63 عملية تخفيض! في الواقع ، كل قطع يزيد من عدد الأجزاء بواحد ؛ في نفس الوقت ، في اللحظة الأولى لدينا جزء واحد (اللوحة نفسها) ، وفي اللحظة الأخيرة - 64 (جميع مجالات اللوحة).
أرز. 7. ثلاث مشاكل على لوحة غير عادية |
في المهمة في الشكل. 7 أ ، تحتاج إلى إكمال ثلاث مهام ، واحدة رياضية واثنتان شطرنج بحت:
أ) قطع اللوح إلى أربعة أجزاء متطابقة ؛
ب) كش ملك للملك الأسود في أقصر طريقة عندما يتحرك الأبيض ؛
ج) كش ملك للملك الأسود في أقصر الطرق ؛ بينما يتحرك الأسود ، يلعب المؤمنون بشكل تعاوني).
الحلول: أ) كيفية قص اللوح كما هو مبين في الشكل. 7 ب ؛ ب) عندما يتحرك الأبيض ، يتم إعطاء كش ملك في الحركة الثانية عشرة: 1-12. Be1-b4، Ke3-d3-c4، Be4-c2-b3، Kc4-c3، Bb4-d6، Bb3-d5، Kc3-c2، Bd6-c5، Bd5-c4، Bd6-b4كش ملك (جميع تحركات الملك الأسود إجبارية ولا يتم تقديمها) ؛ ج) مع اللعب الصحيح بعد 1. ... كش ملك Ke6-e7 مستحيل ، لأن الملك الأسود يختبئ في e8 - 2. Be1-b4 + Ke7-e8 ، ويضطر الأسقف ذو التربيع المظلم إلى ترك قطري a3 - e7 بسبب تهديد الجمود. ومع ذلك ، إذا لعب الأسود بشكل تعاوني (مساعدة زميله الأبيض) ، فسيتم الوصول إلى الهدف في ثلاث حركات فقط:
1. ... Ke6-d6
2. Ke3-d4 Ke6-e7
3. Be1-b4 + Ke7-e6
4. Be4-d5 ماتي.لا يتم استخدام عدد من الحقول في لوحتنا أثناء التزاوج ، ولكن إذا تم استبعادها ، فلن تكون هناك مشكلة في قطع السبورة.
أرز. 8. التناقض مع قطع رقعة الشطرنج: أ) 8 × 8 = 64. ب) 13 × 5 = 65 |
فكر الآن في مفارقة معروفة مرتبطة بقطع رقعة الشطرنج. قمنا بتقطيع اللوحة إلى أربعة أجزاء ، كما هو موضح في الشكل. 8 ، أ (في هذه الحالة ، من غير المربح لنا تلوين حقولها) ، ومن الأجزاء الناتجة سنضيف مستطيلًا (الشكل 8 ، ب). مساحة اللوح هي 64 ، ومساحة المستطيل الناتج 65. وهكذا ، عند قص اللوح ، جاء حقل إضافي من مكان ما!
الحل للمفارقة هو أن رسوماتنا ليست دقيقة تمامًا (لقد رسمنا عمدًا خطوطًا سميكة لإخفاء عدم الدقة). مع البناء الدقيق للرسم في الشكل. 8 ب ، بدلاً من المستطيل المائل ، سيظهر شكل ماسي ممدود قليلاً بجوانب تبدو وكأنها مندمجة تقريبًا. ستكون مساحة هذا الشكل مساوية للوحدة "الإضافية".
ابتكر المروج المعروف للرياضيات في بداية القرن ، إيغناتيف ، "طريقة رقعة الشطرنج" ، التي تسمح باشتقاق صيغ مختلفة. نعطي مثالين بسيطين حول هذا الموضوع.
لنجد مجموع أول n من الأعداد الطبيعية باستخدام "طريقة رقعة الشطرنج". للقيام بذلك ، على السبورة (ن + 1) × ن (في الشكل 9 ، أ ن = 8) نقوم بتلوين جميع حقول العمود الرأسي الأول ، جميع حقول العمود الثاني (باستثناء الحقل العلوي) ، العمودي الثالث (باستثناء العلويتين) ، إلخ. د ، وأخيراً - أسفل المجال nعمودي. نتيجة لذلك ، ستكون الحقول البيضاء والسوداء على لوحتنا متساوية ، أي 1 + 2 + ... + n. نظرًا لأن اللوحة بأكملها تتكون من حقول n (n + 1) ، فإننا نحصل عليها
2 (1 + 2 + ... + ن) = ن (ن + 1) ،
من أين تتبع الصيغة المعروفة لمجموع التقدم الحسابي:
1 + 2 + ... + n = n (n + 1) / 2.
الآن دعنا نثبت الصيغة التالية:
8 (1 + 2 + ... + n) + 1 = (2n + 1) ².
للقيام بذلك ، خذ لوحة (2n + 1) × (2n + 1) وقم برسم عدد من حقولها باللون الأسود ، كما هو موضح في الشكل. 9 ، 6 (للحالة ن = 5). من الواضح أن كل جزء أسود يحتوي على حقول (1 + 2 + ... + n). بدون الأخذ بعين الاعتبار المجال المركزي ، لدينا هنا أربعة أجزاء متطابقة بيضاء وسوداء. الصيغة المطلوبة تأتي من حقيقة أن لوحتنا تحتوي على حقول (2n + 1) ² وتتكون من حقل مركزي وثمانية أجزاء متطابقة (أربعة بيضاء وأربعة سوداء - الشكل 9 ب).
عند كشف التناقض ، بالإضافة إلى التعرف على "طريقة رقعة الشطرنج" ، يمكن استبدال اللوحة نفسها بأمان بورقة مربعة أو طاولة. هناك عدد كبير من المشكلات المتعلقة بمثل هذه الأشياء ، لكن دراستها التفصيلية ستأخذنا بعيدًا جدًا عن لعبة الشطرنج.
في ختام الفصل ، نقدم دليلًا قديمًا على رقعة الشطرنج ... لنظرية فيثاغورس. ارسم مربعًا على السبورة ، كما هو موضح في الشكل. 10 ، أ. ينقسم اللوح إلى هذا المربع وأربعة مثلثات قائمة الزاوية. على التين. 10 ، 6 نرى نفس المثلثات الأربعة ، بالإضافة إلى مربعين. لذا ، فإن المثلثات في كلتا الحالتين تشغل نفس المنطقة. وبالتالي ، فإن الأجزاء المتبقية من اللوحة التي لا تحتوي على مثلثات تحتل نفس المنطقة ، في الشكل. 10 ، أ - مربع واحد ، وفي الشكل. 10 ب - اثنان. بما أن المربع الكبير مبني على وتر المثلث القائم ، والمربعات الصغيرة على رجليه ، فإن "سروال فيثاغورس متساوٍ في كل الاتجاهات"!
بالطبع ، بالمعنى الدقيق للكلمة ، لا يثبت تفكيرنا نظرية فيثاغورس (تمت دراسة حالة معينة فقط) ، ولكنه يوضحها فقط. لكن مثل هذا الدليل لا يستخدم رقعة الشطرنج - بالنسبة لأي مثلث قائم الزاوية ، يمكنك اختيار مربع ينكسر بطريقة مماثلة.
هذا هو الحل الذي تم تقديمه في كتاب T. Saati "طرق التحسين الصحيحة والمشكلات المتطرفة ذات الصلة" (M. ، "Mir" ، 1973).
إس. جولومب. بوليومينو. م ، مير ، 1974.
وقد تم إثبات ذلك من قبل A. Soifer في مقالة "Checkered board and polymipo" ("Kvant"، 1972، No. 11)؛ هناك عدد من مشاكل البوليومينو الجديدة.
إيغناتيف. في عالم الإبداع أو الحساب للجميع. الكتاب. 1 - 3. م - Pg.، Gosizdat، 1923.
في هذا الدرس ، سنتحدث عن صفحات التلوين وكيف تساعد في حل المشكلات. ضع في اعتبارك مشاكل القطع والتبليط غير القياسية وطرق حلها.
ملخص درس "القطع. التغطية بالفسيفساء. التلوين".
صفحات التلوين. قطع. الفسيفساء.
كان العديد من العلماء مغرمين بقطع المشاكل منذ العصور القديمة. تم العثور على حلول للعديد من مشاكل القطع البسيطة من قبل الإغريق والصينيين القدماء ، لكن أول مقالة منهجية حول هذا الموضوع كتبها أبو الفيف ، عالم الفلك الفارسي الشهير في القرن العاشر ، والذي عاش في بغداد. انخرطت المقاييس بجدية في حل مشاكل قطع الأشكال إلى أقل عدد من الأجزاء ثم تكوين شخصية جديدة أو أخرى منها في بداية القرن العشرين فقط. كان أحد مؤسسي هذا الفرع الرائع من الهندسة هو مترجم اللغز الشهير Henry E. Dudeney. تم كسر عدد كبير بشكل خاص من سجلات قطع الأرقام الموجودة مسبقًا بواسطة خبير في مكتب براءات الاختراع الأسترالي ، هاري ليندغرين. إنه قاطع شخصية قيادي.
اليوم ، عشاق الألغاز مغرمون بحل مشاكل القطع ، ويرجع ذلك أساسًا إلى عدم وجود طريقة عالمية لحل مثل هذه المشكلات ، ويمكن لأي شخص يتعامل مع حلها أن يثبت بشكل كامل براعته وحدسه وقدرته على التفكير الإبداعي. نظرًا لعدم الحاجة إلى معرفة عميقة بالهندسة هنا ، يمكن للهواة في بعض الأحيان أن يتفوقوا على علماء الرياضيات المحترفين.
لإثبات أنه من الممكن حل مشكلة تقطيع بعض الأشكال إلى أجزاء ، يكفي توفير نوع من طريقة القطع. العثور على جميع الحلول ، أي جميع طرق القطع ، هو أصعب قليلاً. وإثبات أن القطع مستحيل هو بالفعل صعب للغاية. في بعض الحالات ، يساعدنا تلوين الشكل على القيام بذلك.
مهمة 1:أخذنا مربعًا من الورق المتقلب مقاس 8 × 8 ، وقطعنا خليتين منه (أسفل اليسار وأعلى اليمين). هل من الممكن تغطية الشكل الناتج بالكامل باستخدام "الدومينو" - 1 × 2 من المستطيلات؟
المهمة 2.هل من الممكن وضع رقعة شطرنج بها 32 قطعة دومينو بحيث يتم وضع 17 قطعة منها أفقيًا و 15 قطعة رأسياً؟
المهمة 3:هل من الممكن قص مربع من الورق المتقلب بالحجم
4 × 4 لقاعدة واحدة ، ومربع واحد ، وعمود واحد ، ومتعرج واحد؟
المهمة 4:هل من الممكن رسم مربع 8 × 8 باستخدام 15 1 × 4 مستطيل وزاوية عرض واحدة؟
المهمة 5:هل من الممكن رسم مستطيل 6 × 10 به 1 × 4 مستطيلات؟
المهمة 6:هل من الممكن طي مربع 6 × 6 باستخدام 11 مستطيلاً × 3 وزاوية عرض واحدة؟
المهمة 7:توجد خنفساء على كل خلية في لوحة 5 × 5. في وقت ما ، تقلع جميع الخنافس وتهبط على الخلايا المجاورة على الجانب. إثبات أنه سيكون هناك واحد على الأقل قفص فارغ.
المهمة 8:قطع قفص زاوية من لوح 8 × 8. هل يمكن تقطيع الباقي إلى مستطيلات 3 × 1؟
المهمة 9:تتحرك قطعة الجمل على رقعة الشطرنج بحركة مثل (١ ، ٣). هل يمكن نقل "الجمل" من الحقل العشوائي إلى الحقل المجاور؟
المهمة 10:هل يمكن تغطية لوحة 10 × 10 بأشكال من النموذج؟
المهمة 11:بالنظر إلى لوحة 12 × 12. يوجد 9 قطع في الزاوية اليسرى السفلية ، تشكل مربع 3 × 3. في حركة واحدة ، يمكنك اختيار بعض قطعتي الداما وإعادة ترتيب أحدهما بشكل متماثل بالنسبة للآخر (دون مغادرة اللوحة) . هل من الممكن تحريك هذه القطع في عدة حركات بحيث تشكل مربع 3 × 3 في الركن الأيمن السفلي؟
المهمة 12:توجد خنفساء في كل خلية مربعة 9 × 9. بناءً على الأمر ، تطير كل خنفساء إلى إحدى الخلايا المجاورة قطريًا. إثبات أن 9 خلايا على الأقل ستكون مجانية بعد ذلك.
المهمة 13:القلعة على شكل مثلث منتظم ، مقسمة إلى 25 قاعة صغيرة من نفس الشكل. تم عمل باب في كل جدار بين الصالات. يتجول المسافر حول القلعة دون زيارة أي من القاعات أكثر من مرة. ابحث عن أكبر عدد من القاعات يمكنه زيارتها. 
المهمة 14:ما هو أقصى عدد من المعينات التي يمكن تقطيعها إلى مثلث متساوي الأضلاع مقسومًا إلى 36 مثلثًا متساوي الأضلاع؟
المهمة 15.هناك 16 قطعة 1x3 وبلاط واحد 1x1 في مربع 7x7. أثبت أن قطعة 1 × 1 تقع إما في المركز أو مجاورة لحدود المربع.
المهمة 16.في الزاوية اليسرى السفلية من رقعة الشطرنج 8 × 8 ، يتم وضع تسعة رموز على شكل مربع 3 × 3. يمكن أن تقفز الشريحة إلى حقل حر من خلال شريحة قريبة ، أي يمكن أن تنعكس بشكل متماثل حول مركزها (يمكنك القفز عموديًا وأفقيًا وقطريًا). هل من الممكن لعدد معين من هذه الحركات أن يضع كل الرقائق مرة أخرى في شكل مربع 3 × 3 ، ولكن في زاوية مختلفة.
