חידות מתמטיות

[godlin23]

1. recursion problem
int foo(int n)zz
if n==0 return 1
if n<0 return 0

return foo(n-1)+foo(n-2)zzz

zz are for readability

 

[dk91]

בשאלה עם הקוף ננסה לדחוק את הקוף לפינה על ידי הליכה מקצה אחד ועד הקצה השני אבל נרצה לבחור כסא שיש מסביבו שתי כיסאות ולכן את הקיצוניים נוריד , עכשיו נרסס את הקוף נגיד מ9 עד 2 ואז מ2 ועד 9 הריסוס של 2 ו9 פעמיים מבטיח מצב שאם הוא היה בקצוות וקיפץ בין 10 ל9 10 ל9 אז זה יתפוס את המצב הזה ויהרוג אותו , כנ"ל לגבי 2 ו1 2 ו1 פשוט צריך לצייר ולראות עכשיו בדרך חזור נגיד מ2 ל9 אפשר לחשוב שהקוף יוכל לקפץ לכסא הנגדי ושהמצב הזה לא יתפס בחזור אבל הוא כן כי ברגע שבקצה אנחנו יורים פעמיים זה יוצר מרווח אי זוגי בין הקוף לירייה ולכן הוא לא יכול לקפץ ביירייה הבאה מעליו אלא רק להגיע לכסא הבא שהוא ירה עליו או לקפוץ ימינה שוב במקרה שחוזרים מ2 ל9 ואז עדיין לשמור על מרווח אי זוגי ובסופו של דבר הוא יתפוס בקצה הימני , טיפה קשה להסביר את זה אבל ניסיתי כמיטב יכולתי....
בסופו של דבר התשובה היא שיקח לו 16 יריות להגיע אליו במקרה הנ"ל

 

[Majin Buu]

בשאלה עם הקוף ננסה לדחוק את הקוף לפינה על ידי הליכה מקצה אחד ועד הקצה השני אבל נרצה לבחור כסא שיש מסביבו שתי כיסאות ולכן את הקיצוניים נוריד , עכשיו נרסס את הקוף נגיד מ9 עד 2 ואז מ2 ועד 9 הריסוס של 2 ו9 פעמיים מבטיח מצב שאם הוא היה בקצוות וקיפץ בין 10 ל9 10 ל9 אז זה יתפוס את המצב הזה ויהרוג אותו , כנ"ל לגבי 2 ו1 2 ו1 פשוט צריך לצייר ולראות עכשיו בדרך חזור נגיד מ2 ל9 אפשר לחשוב שהקוף יוכל לקפץ לכסא הנגדי ושהמצב הזה לא יתפס בחזור אבל הוא כן כי ברגע שבקצה אנחנו יורים פעמיים זה יוצר מרווח אי זוגי בין הקוף לירייה ולכן הוא לא יכול לקפץ ביירייה הבאה מעליו אלא רק להגיע לכסא הבא שהוא ירה עליו או לקפוץ ימינה שוב במקרה שחוזרים מ2 ל9 ואז עדיין לשמור על מרווח אי זוגי ובסופו של דבר הוא יתפוס בקצה הימני , טיפה קשה להסביר את זה אבל ניסיתי כמיטב יכולתי....
בסופו של דבר התשובה היא שיקח לו 16 יריות להגיע אליו במקרה הנ"ל

אתה לא יכול לדחוק אותו לפינה כי נניח דהוא נמצא בכיסא 8 וירית כרגע על כיסא 7, הוא יקפוץ לכיסא 7 ואתה תמשיך לכיסא 8, 9, 10 בזמן שהוא יכול להיות ב4

 

[godlin23]

שאלת הקוף:
עריכה: חושב על זה.

 

[DorT]

הוכח שבקבוצה שיש בה n אנשים, לפחות 2 אנשים מכירים בדיוק אותו מספר של אנשים.
הנחה: אם אדם X מכיר את Y, אז Y מכיר את X.

 

[dk91]

זה נקרא עקרון שובך היונים יש לנו N אנשים ולכן לכל בן אדם יש N-1 אפשרויות הכרות במקסימום כי הבן אדם עצמו לא נחשב כמי שמכיר את עצמו.
לכן אם יש לנו בסה"כ N אנשים אבל N-1 אפשרויות הכרות כלומר בהכרח חייבים להיות שניים שיכירו את אותה כמות אנשים.
זה כמו שיהיה לנו 9 שובכים ו10 יונים אז בהכרח יהיו 2 יונים באותו שובך.
יום טוב!

 

[DorT]

שאלת הקוף:
אני יתחיל ממקום 1, ויתחיל לראות כל פעם לאותו כיסא פעמיים ואז יתקדם צעד, סה"כ 19 יריות במקרה הגרועה.
הסיבה שאני לא יפספס היא אם הוא היה בכיסא 1 הרגתי אותו, אם הוא היה בכסא 2 וקפץ לאחד לאחר הירי הרגתי אותו. ולכן לאחר הירי מובטח לי שהוא לא יהיה בכיסא 1.
וככה נעשה לכל כיסא, בסוף הוא יוכל להתחבות רק בכסא ה 10 שם אני יפגע בו ב 100%

זה לא נכון כי נניח וירית פעמיים לכיסא הכי ימני. אחרי היריה השנייה יכול להיות שהקוף קפץ לכיסא הכי ימני. אחרי הירייה השניה אתה לא יודע אם הקוף נמצא בקצה או לא.
לא בטוח שהבתי את 9 עד הסוף.
אם כן:
עריכה: זה ממש לא נכון

 

[Majin Buu]

שאלת הקוף:
אני יתחיל ממקום 1, ויתחיל לראות כל פעם לאותו כיסא פעמיים ואז יתקדם צעד, סה"כ 19 יריות במקרה הגרועה.
הסיבה שאני לא יפספס היא אם הוא היה בכיסא 1 הרגתי אותו, אם הוא היה בכסא 2 וקפץ לאחד לאחר הירי הרגתי אותו. ולכן לאחר הירי מובטח לי שהוא לא יהיה בכיסא 1.
וככה נעשה לכל כיסא, בסוף הוא יוכל להתחבות רק בכסא ה 10 שם אני יפגע בו ב 100%

נגיד והקוף בכיסא 6 וסיימת לירות על כיסא 5
עכשיו הוא יעבור לכיסא 5 ואתה ל6

 

[Balbazor]

אתה בטוח שהשאלה מנוסחת טוב? אני מתחיל להתייאש
כאילו אם הקוף בכיסא x ואתה יורה בכיסא x-1 הוא עדיין אחכ יכול לעבור לכיסא x-1 ואצה לx וככה זה לא ייגמר
אז אם לא הולכים מהצד לירות בכל השורה או משהו אי אפשר להיות בטוח בשופ כיסא שהוא לא שם
אסור להרוג קופים

מנוסחת טוב מאוד. יש דרך בה הורגים אותו בוודאות 100%

בשאלה עם הקוף ננסה לדחוק את הקוף לפינה על ידי הליכה מקצה אחד ועד הקצה השני אבל נרצה לבחור כסא שיש מסביבו שתי כיסאות ולכן את הקיצוניים נוריד , עכשיו נרסס את הקוף נגיד מ9 עד 2 ואז מ2 ועד 9 הריסוס של 2 ו9 פעמיים מבטיח מצב שאם הוא היה בקצוות וקיפץ בין 10 ל9 10 ל9 אז זה יתפוס את המצב הזה ויהרוג אותו , כנ"ל לגבי 2 ו1 2 ו1 פשוט צריך לצייר ולראות עכשיו בדרך חזור נגיד מ2 ל9 אפשר לחשוב שהקוף יוכל לקפץ לכסא הנגדי ושהמצב הזה לא יתפס בחזור אבל הוא כן כי ברגע שבקצה אנחנו יורים פעמיים זה יוצר מרווח אי זוגי בין הקוף לירייה ולכן הוא לא יכול לקפץ ביירייה הבאה מעליו אלא רק להגיע לכסא הבא שהוא ירה עליו או לקפוץ ימינה שוב במקרה שחוזרים מ2 ל9 ואז עדיין לשמור על מרווח אי זוגי ובסופו של דבר הוא יתפוס בקצה הימני , טיפה קשה להסביר את זה אבל ניסיתי כמיטב יכולתי....
בסופו של דבר התשובה היא שיקח לו 16 יריות להגיע אליו במקרה הנ"ל

יפה מאוד! פתרון נכון.

הוכח שבקבוצה שיש בה n אנשים, לפחות 2 אנשים מכירים בדיוק אותו מספר של אנשים.
הנחה: אם אדם X מכיר את Y, אז Y מכיר את X.

פתרון: נניח בשלילה שלא קיימים לפחות 2 אנשים שמכירים בדיוק אותם אנשים - כלומר כל אדם מכיר מספר שונה של אנשים.
ברור כי מס' האנשים שבנאדם יכול להכיר נע מ0 (לא מכיר אף אחד) עד לn-1 (מכיר את כולם, חוץ מעצמו כמובן).
ההתאמה היחידה שהיא חד-חד ערכית ועל לפי התנאי שאמרנו (כל אחד מכיר מס' שונה) היא שהאדם הראשון מכיר 0, השני 1, וכו' עד לבנאדם הn שמכיר n-1 אנשים.
אבל קיבלנו סתירה - אם הבנאדם הn מכיר n-1 אנשים זה אומר שהוא בהכרח מכיר את כולם, כולל את האדם שמכיר 0 אנשים, אבל מהסימטריות של התכונה "להכיר" נקבל שהאדם שמכיר 0 חייב להכיר את האדם שמכיר n-1, בניגוד לתנאי.
לכן הוכחנו בשלילה שחייב להיות שלפחות 2 אנשים מכירים את אותו מספר אנשים.

 

[DorT]

פתרון: נניח בשלילה שלא קיימים לפחות 2 אנשים שמכירים בדיוק אותם אנשים - כלומר כל אדם מכיר מספר שונה של אנשים.
ברור כי מס' האנשים שבנאדם יכול להכיר נע מ0 (לא מכיר אף אחד) עד לn-1 (מכיר את כולם, חוץ מעצמו כמובן).
ההתאמה היחידה שהיא חד-חד ערכית ועל לפי התנאי שאמרנו (כל אחד מכיר מס' שונה) היא שהאדם הראשון מכיר 0, השני 1, וכו' עד לבנאדם הn שמכיר n-1 אנשים.
אבל קיבלנו סתירה - אם הבנאדם הn מכיר n-1 אנשים זה אומר שהוא בהכרח מכיר את כולם, כולל את האדם שמכיר 0 אנשים, אבל מהסימטריות של התכונה "להכיר" נקבל שהאדם שמכיר 0 חייב להכיר את האדם שמכיר n-1, בניגוד לתנאי.
לכן הוכחנו בשלילה שחייב להיות שלפחות 2 אנשים מכירים את אותו מספר אנשים.

יפה
פתרון Brute force ל 5 ? באמת? כמה זמן זה אמור לקחת

המתמטיקה שלי חלשה מדי בשבילך השאלה הזאת אבל משתמשים פה במשפט הגבול המרכזי ומפתחים את זה?

 

[Balbazor]

יפה
פתרון Brute force ל 5 ? באמת? כמה זמן זה אמור לקחת

המתמטיקה שלי חלשה מדי בשבילך השאלה הזאת אבל משתמשים פה במשפט הגבול המרכזי ומפתחים את זה?

לא הרבה - במטלב סיימתי 100 אלף איטרציות תוך כמה דקות. פשוט צריך לכתוב את הקוד חכם שלא יעשה יותר פעולות ממה שהוא צריך.

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

 

[GuyDBG]

קחו חידה: תמצאו בדרך הכי יעילה את הרצף הכי ארוך של מספרים ראשוניים שהסכום שלהם הוא מספר ראשוני שקטן ממיליון

פרס כספי לפותר

אתה לא יכול לדחוק אותו לפינה כי נניח דהוא נמצא בכיסא 8 וירית כרגע על כיסא 7, הוא יקפוץ לכיסא 7 ואתה תמשיך לכיסא 8, 9, 10 בזמן שהוא יכול להיות ב4

הוא לא יגיע למצב שתיארתי כי הוא שומר על מרווח אי זוגי
נגיד ואני ב2
אני יורה עליו פעמיים
אם יש מישהו ב3, או שהוא יקפוץ ל2 ובירייה הבאה ימות או שהוא יקפוץ ל4
עכשיו נגיד והוא ב4, אז בירייה הבאה שלי על 2 הוא יקפוץ ל3 או ל5
אם זה ל3 אז הוא ימות בירייה הבאה שלי, אם הוא קופץ ל5 אז כשאני ירה על 3 הוא יקפוץ או ל4 וימות או ל6, ואז כשאני ירה על 5 ככה זה ימשיך. כל פעם או שהוא ימות או שהמרווח האי זוגי (או הזוגי, תלוי אם אתה סופר לפני או אחרי הירייה) ישמר

 

[Balbazor]

קחו חידה: תמצאו בדרך הכי יעילה את הרצף הכי ארוך של מספרים ראשוניים שהסכום שלהם הוא מספר ראשוני שקטן ממיליון

פרס כספי לפותר

לקחתי את כל המספרים הראשוניים שקטנים ממליון ודחפתי למטלב.
דבר ראשון היה למצוא את הסכום של n המספרים הראשוניים הראשונים שמגיע למעל מליון - יצא 547. כבר יש חסם עליון לבעייה.
על הדרך (כי אני כבר עושה את האיטרציות) בדקתי אם הסכום הוא ראשוני (ע"י חיפוש בינארי במערך, סה"כ סיבוכיות של בערך O(16).
קיבלתי שהסכום של 536 הראשוניים הראשונים הוא ראשוני, (958577), יש חסם תחתון.

השלב הבא זה עבור כל k בין 537 ו546 לחשב את הסכום של k-1 הראשוניים הראשונים, ואז להוסיף את הראשוני הk+1, הk+2 וכו' כדי לראות מתי מגיעים מעל מליון. כעת עבור k כזה יש לנו חסם על המספר הראשוני המקסימלי שיכול להיות בסכום. עכשיו כבר מרחב האפשרויות שלנו הצמטמצם מאוד (בהערכה גסה חסום ע"י 10E19), אבל צריך לצמצם עוד. אפשר אולי לצמצם על סמך זה שהסכום חייב להיות אי-זוגי, אז נוכל לפסול כמחצית מהסכומים על סמך האם 2 מופיע בהם ומספר המחוברים שבהם.
עריכה: בעצם במחשבה שנייה זה יצא הרבה יותר ממחצית.

השאלה מה הפרס הכספי כדי לדעת אם יש טעם לבזבז על זה עוד זמן 😴

 

[GuyDBG]

לקחתי את כל המספרים הראשוניים שקטנים ממליון ודחפתי למטלב.
דבר ראשון היה למצוא את הסכום של n המספרים הראשוניים הראשונים שמגיע למעל מליון - יצא 547. כבר יש חסם עליון לבעייה.
על הדרך (כי אני כבר עושה את האיטרציות) בדקתי אם הסכום הוא ראשוני (ע"י חיפוש בינארי במערך, סה"כ סיבוכיות של בערך O(16).
קיבלתי שהסכום של 536 הראשוניים הראשונים הוא ראשוני, (958577), יש חסם תחתון.

השלב הבא זה עבור כל k בין 537 ו546 לחשב את הסכום של k-1 הראשוניים הראשונים, ואז להוסיף את הראשוני הk+1, הk+2 וכו' כדי לראות מתי מגיעים מעל מליון. כעת עבור k כזה יש לנו חסם על המספר הראשוני המקסימלי שיכול להיות בסכום. עכשיו כבר מרחב האפשרויות שלנו הצמטמצם מאוד (בהערכה גסה חסום ע"י 10E19), אבל צריך לצמצם עוד. אפשר אולי לצמצם על סמך זה שהסכום חייב להיות אי-זוגי, אז נוכל לפסול כמחצית מהסכומים על סמך האם 2 מופיע בהם ומספר המחוברים שבהם.
עריכה: בעצם במחשבה שנייה זה יצא הרבה יותר ממחצית.

השאלה מה הפרס הכספי כדי לדעת אם יש טעם לבזבז על זה עוד זמן 😴

תגיד גם איך מצאת את הראשוניים שקטנים ממיליון

 

[Balbazor]

תגיד גם איך מצאת את הראשוניים שקונים ממיליון

חיפשתי בגוגל first prime numbers that are smaller than 1000000 ועשיתי קופי פייסט

 

[GuyDBG]

חיפשתי בגוגל first prime numbers that are smaller than 1000000 ועשיתי קופי פייסט

לא טוב גבר. תחשב בעצמך

 

[Balbazor]

לא טוב גבר. תחשב בעצמך

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

אגב - ברצף אתה מתכוון מספרים עוקבים או לא בהכרח? אם כן אז מספר האפשרויות קטן כבר לפחות מ1000.

 

[GuyDBG]

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

אגב - ברצף אתה מתכוון מספרים עוקבים או לא בהכרח? אם כן אז מספר האפשרויות קטן כבר לפחות מ1000.

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

 

[Balbazor]

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

אפשר לעשות את זה built-in בקפיצות של 2, 3, 5, וכו'. זה פשוט מסבך קצת את הקוד. אפשר להוריד אפילו את תנאי החלוקה ולהרחיב את האיטרציה.
אפשר גם לעשות את האלגוריתם דינאמי, וברגע שמצאנו מספר ראשוני נוסיף אותו לרשימת הקפיצות, אבל אני חושב שזה יקח יותר זמן מריצה ממעבר פשוט על פני המספרים. סה"כ אנחנו חסומים במליון - זו לא סיבוכיות פסיכית לחישוב ראשוניות.
לחישוב סכומים חלקיים זו כבר כן קבוצה גדולה מדי לbrute force, אבל לא רואה בעיית יעילות חמורה מדי בבדיקת ראשוניות.

 

[GuyDBG]

אפשר לעשות את זה built-in בקפיצות של 2, 3, 5, וכו'. זה פשוט מסבך קצת את הקוד. אפשר להוריד אפילו את תנאי החלוקה ולהרחיב את האיטרציה.
אפשר גם לעשות את האלגוריתם דינאמי, וברגע שמצאנו מספר ראשוני נוסיף אותו לרשימת הקפיצות, אבל אני חושב שזה יקח יותר זמן מריצה ממעבר פשוט על פני המספרים.

לא צריך לרוץ על כל המספרים (גם לא בקפיצות) ועל כל אחד להפעיל פונקציה מסוימת (אפילו אם היא מאוד יעילה) כדי להשיג מהם רק את הראשוניים
אפשר לעשות פעולה מסוימת על כל הרשימה ולסנן מתוכה את הראשוניים (זה לא קשה במיוחד אבל משפר את הזמן ריצה בהרבה)