חידת ילדים

[בחשכת הלילה]

התווכחתי עם חבר על רמת הקושי של החידה הבאה. במהלך אחד אפשר להזיז עיגול אחד למשבצת סמוכה פנויה. בכמה מהלכים יוכלו שני העיגולים הכחולים להתחלף במקומותיהם עם שני העיגולים האדומים? מהו מספר המהלכים המינימלי?

 

[בחשכת הלילה]

התווכחתי עם חבר על רמת הקושי של החידה הבאה. במהלך אחד אפשר להזיז עיגול אחד למשבצת סמוכה פנויה. בכמה מהלכים יוכלו שני העיגולים הכחולים להתחלף במקומותיהם עם שני העיגולים האדומים? מהו מספר המהלכים המינימלי?

חבל שאי אפשר לראות בו זמנית את השאלה ואת הסרטוט.

 

[הפרבולה1]

התווכחתי עם חבר על רמת הקושי של החידה הבאה. במהלך אחד אפשר להזיז עיגול אחד למשבצת סמוכה פנויה. בכמה מהלכים יוכלו שני העיגולים הכחולים להתחלף במקומותיהם עם שני העיגולים האדומים? מהו מספר המהלכים המינימלי?

 

[הפרבולה1]

יצא לי 32 צעדים, נראה לי שזה המינימום ( אולי אפשר להוכיח באמצעות מחשב , מספר המסלולים האפשריים בלי לחזור על עצמם הוא סופי )

 

[עריסטו]

יצא לי 32 צעדים, נראה לי שזה המינימום ( אולי אפשר להוכיח באמצעות מחשב , מספר המסלולים האפשריים בלי לחזור על עצמם הוא סופי )

צפה בקובץ המצורף 104953

בפתרון שלך יש 40 צעדים. המחשב מאשר שזהו המספר המינימלי. בטבלה הבאה המספר הימני הוא מספר הצעדים, והמספר השמאלי הוא מספר המצבים שדורשים את מספר הצעדים הזה:
0 1
1 2
2 3
3 5
4 7
5 10
6 13
7 16
8 21
9 30
10 41
11 53
12 55
13 50
14 41
15 35
16 35
17 44
18 47
19 50
20 49
21 43
22 34
23 29
24 24
25 21
26 20
27 19
28 19
29 23
30 29
31 41
32 48
33 48
34 43
35 38
36 34
37 33
38 29
39 24
40 18
41 13
42 8
43 6
44 4
45 2
46 1
47 1
אין מצב שדורש 48 צעדים או יותר (ואין מצב של הכלים שאי אפשר להגיע אליו). המצב היחיד שדורש 47 צעדים הוא כאשר ארבעת המשבצות הימניות תפוסות - שני הכלים הכחולים ומשמאלם שני הכלים האדומים. אם מסירים מלוח המשחק את שתי המשבצות הימניות (שאין להן תפקיד בפתרון), הטבלה נראית כך:
0 1
1 2
2 3
3 5
4 7
5 8
6 9
7 10
8 12
9 17
10 22
11 22
12 14
13 7
14 5
15 5
16 8
17 12
18 15
19 17
20 18
21 17
22 15
23 12
24 8
25 5
26 4
27 4
28 5
29 8
30 12
31 15
32 17
33 14
34 12
35 15
36 16
37 12
38 6
39 3
40 1
כעת אין מצב שדורש 41 צעדים או יותר (ואין מצב של הכלים שאי אפשר להגיע אליו) והמצב היחיד שדורש 40 צעדים הוא מצב היעד של החידה המקורית.

 

[הפרבולה1]

בפתרון שלך יש 40 צעדים. המחשב מאשר שזהו המספר המינימלי. בטבלה הבאה המספר הימני הוא מספר הצעדים, והמספר השמאלי הוא מספר המצבים שדורשים את מספר הצעדים הזה:

אכן טעיתי בספירה - יש 40 צעדים ( ולא 32 )

 

[יוביוב הירוק]

בהתייחס לרמת הקושי - שים לב שהחידה אינה "מה מספר המהלכים הנמוך ביותר שאתה מצליח לתכנן?", אלא "מהו המספר המינימלי". כלומר נדרש למצוא את האלגוריתם האופטימלי, ולדעת שהוא האופטימלי. נראה לי שזה הקושי.