חידה יפה

[טיקטי]

חידה יפה

על היקפו של מעגל יש n נקודות n-1 ירוקות ואחת אדומה בכל שלב מותר לבחור 3 נקודות רצופות ולהפוך את צבען עבור אילו n-ים ניתן להפוך את כל הנקודות במעגל לירוקות למי שיש את הספר מספר חזק זו חידה מספר 84 עמרי

 

[djdror]

../images/Emo62.gif

לא מכיר את החידה, ועונה ישר מהשרוול. מקווה שלא עושה פאדיחות. יהיה X מספר שלם כלשהו. כדי שאפשר יהיה להפוך את כל הנקודות לירוקות אז צריך להתקיים

N=3X+1​

 

[טיקטי]

פאדיחות? לא נראה לי אבל

יש עוד צורה של מספרים שמקיימת את זה אז קבל

עמרי

 

[mili999]

כמובן שגם

3X+2 (כי ברגע שהפכת (חוץ מ-2, אלא אם בהפיכה אחת הירוק מתהפך פעמיים)

 

[טיקטי]

כל הכבוד ../images/Emo127.gif לשניכם

ד"א למישהו יש חידות שהם גם מתמטיקה וגם הגיון כמו החידה של הטורפים או של הנרות או של הספרים עמרי

 

[טלמון סילבר]

דרך אגב,

יש הוכחה יותר טובה מזו שבספר "מספר חזק", כלומר הרבה יותר קצרה. היא מבוססת על... XOR.

 

[טלמון סילבר]

הכוונה להוכחת

אי האפשרות עבור N=3X. עבור מספרים שאינם מתחלקים ב-3, שתי האפשרויות, פשוט מראים את הדרך לעשות את זה.

 

[טיקטי]

אתה מוכן בבקשה להראות את ההוכחה?

 

[טלמון סילבר]

הוכחה.

נחלק את המעגל באורח שרירותי לשלישיות עוקבות. נסמן למשל ירוק כ-0, ואדום כאחד. נניח, למשל, שכל הנקודות ירוקות, ואז המצב של כל השלישיות הוא: 000 000 000 . . . 000 עכשיו נשים לב, שבטור הימני ביותר יש לנו מספר זוגי של 1-ים (כי 0 הוא מספר זוגי), כנ"ל גם בטור האמצעי, וגם בטור השמאלי. אפשר לומר (אם נשתמש במונח מתחום המחשבים), שה-XOR של כל כל השלישיות הוא 000 (בכל פוזיציה, 0 מתאים למספר זוגי של 1-ים באותה פוזיציה, ו-1 מתאים למספר אי זוגי של 1-ים באותה פוזיציה). עכשיו, קל מאוד לבדוק, שכל היפוך צבעים שנבצע, יהפוך את ה-XOR ל-111. נגיד, למשל, שפגענו בדיוק בשלישיה כלשהי: 000 000 111 000 . . . 000 ואכן עכשיו יש לנו בכל עמודה מספר אי זוגי של 1-ים, כלומר ה-XOR הוא 111. נגיד שלא פגענו בדיוק בשלישיה, אלא הפכנו שלוש נקודות רצופות אחרות, למשל: 000 001 110 000 . . . 000 וכמו שאנו רואים: אותה תוצאה. בקיצור, בכל פעולת היפוך של שלוש נקודות רצופות, אנו משנים את זוגיות כמות ה-1-ים בכל העמודות, ולכן ה-XOR הכללי תמיד יהיה 000 ו-111 לסירוגין, ולכן לעולם לא נגיע למצב של: 100 000 000 . . . 000 שה-XOR שלו הוא 100.

 

[טיקטי]

תודה רבה