שאלה באלגוריתמיקה

[jess y]

שאלה באלגוריתמיקה

אשמח אם מישהו יוכל לעזור לי בשאלה הבאה: מכונת טיורינג מוגבלת סרט היא מכונת טיורינג שבה הראש קורא-כותב אינו יכול לנוע מעבר לחלק של הסרט האינסופי המכיל את הקלט. תהא M מכונת טיורינג מוגבלת סרט בעלת Q מצבים וא"ב בגודל m. נסמן ב-n את אורכה של מחרוזת הקלט ל-M. קונפיגורציה של מכונת טיורינג היא אפיון מלא של מצב המכונה ברגע מסוים: המצב שבו המכונה נמצאת, מיקום הראש הקורא-כותב ותוכן הסרט. הוכיחו שמספר הקונפיגורציות האפשריות של המכונה M הוא Qnm^n

 

[HaifaMan]

מה יש פה להוכיח?

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

 

[jess y]

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

 

[jess y]

עוד שאלה

1) הוכיחו את הטענה הבאה: בהנתן מספר טבעי n וקבוצה S של n+1 מספרים טבעיים, קיימים ב-S שני מספרים a, b כך ש-a=b(mod n כלומר ל-a ול-b יש אותה שארית בחלוקה ב-n. 2) השתמשו בסעיף הנ"ל כדי להוכיח את הטענה הבאה: מספר יפה הוא מספר טבעי המורכב מרצף של אחדים ואחריו רצף של אפסים. למשל 1000, 11110. הטענה: בהנתן מספר טבעי כלשהו n, קיים מספר יפה שהוא כפולה של n. רמז: התבוננו בקבוצה של n+1 מספרים (שונים) שכולם מורכבים מרצף של אחדים.

 

[HaifaMan]

1 זה שובך היונים

נסה לקרוא על זה ולנסות לפתור.

 

[jess y]

תודה. לגבי 1

התשובה שלי היא: השארית שיכולה להתקבל מחלוקה ב-n תהיה אחת מאלה: 0, 1, 2,...n-1 (כלומר n אפשרויות). כיוון שיש n+1 מספרים אז מתחייב, לפי עקרון שובך היונים, שלשני מספרים תתקבל אותה שארית בחלוקה ב-n. אני צודק?

 

[HaifaMan]

../images/Emo47.gif

 

[jess y]

../images/Emo13.gif יש לך אולי רעיון ל-2? הסתבכתי עם זה

 

[HaifaMan]

כן

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

 

[jess y]

עדיין לא פתרתי את זה

אם למשל n=3 אז כפולה של n זה 9 (27 וכו') "קיים מספר יפה שהוא כפולה של n", במקרה זה המספר היפה יהיה 111111111?

 

[HaifaMan]

למשל (יש אינסוף כאלו כמובן).

לא ענית על השאלה שלי

 

[jess y]

עדיין לא נפל לי האסימון ../images/Emo10.gif

לפי סעיף 1, יש לפחות 2 מספרים שלהם אותה שארית חלוקה. אבל איך זה עוזר לי?

 

[HaifaMan]

רמז הבא

אם ל-a ול-b אותה שארית בחלוקה לn, מהי השארית כאשר תחלק את a-b (בהנחה ש-a הגדול מהם) ב-n ?

 

[jess y]

השארית תהיה 0 אז...

זה עדיין לא אומר שקיים מספר יפה בקבוצה שהוא כפולה של n.

 

[HaifaMan]

יאללה נלך איתך עד הסוף

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

 

[jess y]

תודה אבל

אם למשל n=3 והקבוצה S מכילה את המספרים הבאים: 1, 11, 111, 1111. אז ל-1 ו-1111 יש אותה שארית (1) בחלוקה ב-3. ההפרש שלהם הוא 1110. זה אכן מספר יפה אבל זה נחשב כפולה של 3?

 

[HaifaMan]

כן... למה לא? ניסית לחלק 1110 ב3 ולבדוק?

מספר X הוא כפולה של Y אם קיים Z (כולם טבעיים) כך ש X = ZY

 

[jess y]

הבנתי. תודה ../images/Emo13.gif