משולש a,b,c

[עריסטו]

משולש a,b,c

בונים משולש הבנוי מהאותיות a,b,c (ראו קובץ מצורף). המשולש נבנה כך: בצלע העליונה יש 28 אותיות אקראיות. אחר כך כל אות נקבעת לפי שתי האותיות שמעליה: מתחת לשתי אותיות זהות מופיעה אותה אות, ומתחת לשתי אותיות שונות מופיעה האות השלישית. אם נתונה השורה העליונה של המשולש, האם ניתן לחזות מה תהיה האות בקדקוד התחתון של המשולש - בלי לבנות את כל המשולש?

 

[היחיד במינו]

תשובה אינטואיטיבית

זה שיש הכי הרבה. אני מנסה עכשיו לחשוב על הסבר מספק.

 

[עריסטו]

ומה אם יש תיקו?

 

[גיאל]

לא נכון

אם יש בשורה לדוגמא ababab... בשורה הבראה יהיה הכל c וכך הלאה עד הסוף

 

[regit knup]

הנה התשובה...

הנה התשובה

 

[regit knup]

ניראה לי שזה קשור ב.....

רצפים, זאת אומרת אם יש מספר אחד שיש לו את הרצף הכי גדול אז הוא יהיה אחרון. או שגם את הרצף הכי גדול, וגם המספר הכי גדול בשורה.

 

[איייייל]

נראה לי שאפשר

אם נייצג כל אות ע"י מספר אחר (a=0,b=1,c=2), אז הסכום של אות מסויימת ושתי האותיות שמעליה הוא תמיד 0 מודולו 3 (0+1+2 או 0+0+0 או 1+1+1 או 2+2+2). כלומר, האות בשורה התחתונה היא פונקציונל לינארי (בשדה Z3) על השורה העליונה (את המקדמים אפשר לחשב בלי לדעת את האותיות הספציפיות שנבחרו).

 

[איייייל]

המשך

מסתבר שהמקדמים במקרה שלנו הם 2 עבור שתי האותיות הקיצוניות, ו0 עבור כל השאר. כלומר, אם שתי האותיות הקיצוניות זהות אז זו תהיה גם התוצאה, אחרת התוצאה היא האות השלישית.

 

[עריסטו]

../images/Emo127.gif

 

[פוטנציאל לא ממומש]

אפשר אולי הסבר למפגרים?

 

[איייייל]

אני אנסה

נייצג כל אות ע"י מספר (a=0,b=1,c=2). אז, אפשר לראות שהפונקציה שנותנת אות מסויימת כפונקציה של שתי האותיות שמעליה היא z=(2*x+2*y)%3, כאשר x,y הן האותיות העליונות, z היא האות התחתונה, ו t%3 היא השארית של החלוקה של t ב 3. (פשוט תבדוק את כל המקרים ותראה שזה תמיד עובד). ע"י הפעלה חוזרת ונשנית של הכלל הזה אפשר לקבל נוסחאות דומות עבור כל האותיות במשולש, כפונקציה של 28 האותיות העליונות. בפרט, אחת הנוסחאות שמקבלים היא: k=(2*i+2*j)%3, כאשר k היא האות התחתונה ביותר במשולש, ו i,j הן שתי האותיות הקיצוניות בשורה העליונה.

 

[מסית ומדיח]

אם אני לא טועה

זה תלוי רק בשניים הראשונים ובשניים האחרונים בשורה העליונה. אם Z נמצא מתחת ל X ו Y אז:

Z = 2*(X+Y) (mod 3)​

את סכום האיברים (מודולו 3)בכל שורה ניתן לבטא כסכום האיברים בשורה הראשונה כאשר כל איבר מופיע מספר מסויים של פעמים בסכום זה. אנחנו רוצים לראות איך אפשר לבטא את סכום האיברים בשורה האחרונה (איבר אחד) בעזרת איברי השורה הראשונה. אפשר לראות שהאיבר במקום ה-i יופיע 28 מעל i פעמים. מכיוון ש-28 מעל i שווה 0, למעט כאשר i=0,1,27,28 (אם לא התבלבלתי) אזי כל האיברים למעט אלה שציינתי לא משפיעים על הסכום.

 

[איייייל]

התבלבלת קצת

המרחק בין השורה הראשונה לאחרונה הוא 27 ולא 28.