חידות

כללי

חידה 1

נגדיר את הפונקציה $f:\mathbb {N} \rightarrow \mathbb {N}$ שמקבלת מספר טבעי ומחזירה את מספר הספרות האי זוגיות שלו בבסיס 10. למה מתכנס הסכום: $\sum _{i=1}^{\inf }{\frac {f(2^{i})}{2^{i}}}$

חידה 2

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

חידה 3

ישנה גננת ולגננת אינסוף ממתקים, היא מעמידה את n ילדי הגן במעגל ומתחילה לחלק להם ממתקים בסדר הבא: היא נותנת ממתק לילד הראשון, מדלגת ילד אחד, נותנת ממתק לילד הבא, מדלגת שני ילדים וכן הלאה.

עבור איזה ערכי n כל הילדים יקבלו ממתק מתישהו?

חידה 4

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

חידה 5

שני אנשים משחקים משחק. על השולחן יש 9 פתקים עם המספרים מ-1 עד 9. כל אחד בתורו לוקח את אחד הפתקים שעדיין על השולחן. הראשון שיש בידיו 3 פתקים שהסכום שלהם הוא 15 מנצח. למי מהשחקנים יש אסטרטגיה מנצחת?

חידה 6

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

חידה 7

אני מטיל קוביה רגילה עד שסכום ההטלות שלי גדול או שווה 12. מה הערך הסביר ביותר לסכום ההטלות.

חידה 8

יש n טענות בעולם, וכל טענה היא או נכונה או לא נכונה.

ידוע שכל בנאדם צודק על רוב הטענות (מעל חצי). ידוע גם שכל שני אנשים חולקים אחד על השני על רוב הטענות.

כמה אנשים לכל היותר יש בעולם, בסדר גודל?

חידה 9

על לוח משבצות בגודל 7X7 עומדות 49 חיפושיות, אחת על כל משבצת. ברגע מסויים כל חיפושית זזה למשבצת שצמודה עליה במאונך (למעלה, למטה, ימינה או שמאלה). האם יכול להיות שאחרי התזוזה על כל המשבצות תהיה חיפושית?

חידה 10

האם אפשר לכסות לוח משבצות בגודל 8X8 שחסרה לו משבצת באחת הפינות באבני טרימינו (1X3)?

חידה 11

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

בשלב הזה אסיר 1 יוצא ואסיר 2 נכנס לחדר, מסתכל על המנורות, וצריך לנחש מי הייתה המנורה האחרונה. אסיר 2 לא יוכל תמיד להצליח בניחוש אחד, אז נותנים לו k ניחושים.

הראו שאם k≥√n, האסירים יכולים לתאם אסטרטגיה שבה אסיר 2 בהכרח יצליח לנחש מי המנורה האחרונה.

חידה 12

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

חידה 13

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

חידה 14

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

חידה 15

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

חידה 16

בערמה יש 2001 אגוזים, בכל שלב מותר לך לקחת ערמה כלשהי, להוריד ממנה אגוז ולפצל את מה שנשאר לשתי ערמות לא ריקות. האם אפשר להגיע למצב שבו כל הערמות מכילות בדיוק 3 אגוזים

חידה 17

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

חידה 18

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

חידה 19

שי ודין משחקים משחק, על לוח שחמט (8X8) נמצאים 64 מטבעות כל אחד במצב עץ או פלי באקראי. שי מקבל מספר בין 0 ל-63 והוא צריך לשנות את המצב של אחד המטבעות מעץ לפלי או מפלי לעץ. דין מסתכל על הלוח וצריך לנחש מה המספר ששי קיבל. מה האסטרטגיה של שי ודין?

חידה 20

באי יש 13 זיקיות כחולות, 15 זיקיות ירוקות ו-17 זיקיות אדומות. בכל שלב ששתי זיקיות מצבעים שונים נפגשות הן משנות את הצבע שלהן לצבע השלישי. האם יכול להיות שכל הזיקיות יהיו באותו צבע?

חידה 21

44 עצים מסודרים במעגל, על כל עץ עומדת ציפור. בכל שלב שתי ציפורים זזות עץ אחד, אחת עם כיוון השעון ואחת נגד כיוון השעון. האם יכול להיות שכל הציפוריים יהיו על עץ אחד?

חידה 22

יש 6 מספרים שונים בין 1 ל-15. תוכיחו שיש שתי תתי-קבוצות שונות שלהם עם אותו סכום.

חידה 23

לוח משבצות בגודל 6X6 מכוסה באבני דומינו, צריך להוכיח שאפשר להעביר קו אופקי או אנכי שלא חותך אף אבן דומינו

חידות גמדים

חידה 1

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

חידה 2

במעגל עומדים n גמדים ועל הראש של הגמד ה-i יש כובע באחד מ-$a_{i}$ צבעים אפשריים, ברגע מסויים כל גמד צריך לנחש את צבע הכובע שיש לו על הראש. מה התנאי על $\{a_{i}\}_{i=1}^{n}$ כך שבהכרח אחד מהם יוכל לומר את הצבע שעל הראש שלו.

חידה 3

במעגל עומדים n גמדים ועל הראש של כל אחד מהם יש כובע עם מספר טבעי, ברגע מסויים כל גמד צריך לנחש כמה גמדים חובשים כובע אם אותו מספר כמוהו (כולל אותו). הגמדים צריכים לתאם אסטרטגיה כך שלפחות אחד מהם בהכרח יצדוק.

חידה 4

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

חידה 5

n גמדים עומדים בטור, לכל אחד מהם יש על הראש כובע באחד מ-k צבעים אפשריים. כל גמד מסוגל לראות את כל הכובעים שלפניו אבל לא את הכובע של עצמו או את של מי שמאחוריו. הגמדים מנחשים את צבע הכובע שעל הראש שלהם לפי הסדר החל מהגמד שמוסגל לראות את כל האחרים. הגמדים צריכים לתאם אסטרטגיה ככה שלכל היותר אחד מהם יטעה.

מתמטיקה

חידה 1

נתונה חבורה סופית G ותת חבורה ממש H. נניח שהמשלים של H ב-G מוכל במחלקת צמידות של G. הראו כי H מגודל אי זוגי

חידה 2

חידה נחמדה לקראת סוף החגים;

יהי n > 1 מספר טבעי.

יהיו $P_{1},P_{2},Q$ תמורות על הקבוצה $[n]=\{0,1,...,n-1\}$

עבור אילו ערכי n ניתן למצוא תמורות $P_{1},P_{2},Q$ כך ש:

(יש למצוא דוגמה לכל n אפשרי, ולהוכיח עבור n לא אפשריים)

1. $P_{1}+P_{2}\equiv _{n}Q$

2. $P_{1}\cdot P_{2}\equiv _{n}Q$

3. $P_{1}^{P_{2}}\equiv _{n}Q$ ($0^{0}$ לא מוגדר)

כשהפעולות מתקיימות איבר איבר

חידה 3

יהיו $A\in M_{20\times 20}$ מטריצה, $v\in \mathbb {R} ^{20}$ וקטור ו-$\phi \in {\mathbb {R} ^{20}}^{\ast }$ פונקציונל לינארי, נתונה הסדרה $a_{n}=\phi (A^{n}\cdot v)$ עבור $1\leq n\leq 1000$ האם אפשר לדעת את $a_{1001}$ כש:

1. $A,\phi$ ידועים אבל $v$ לא ידוע
2. $\phi$ ידוע אבל $v,A$ לא ידועים

חידה 4

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

חידה 6

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

מה הם כל הגרפים שיש בהם בדיוק שני קודקודים מאותה הדרגה?

הסתברות

חידה 1

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

בסדר קושי עולה:

א. אם לוקחים חתיכה אקראית, מה תוחלת האורך?

ב. אם מטילים כפית באקראי ולוקחים את החתיכה שבה היא פגעה, מה תוחלת האורך?

ג. מה תוחלת אורך החתיכה המינימלית

ד. מה תוחלת אורך החתיכה המקסימלית

חידה 2

אני מגריל שני מספרים בקטע (0,1) בהסתברות אחידה. אני אחר כך מחשב את היחס בינהם ומעגל אותו לשלם הקרוב ביותר. מה הסיכוי שהוא זוגי

חידה 3

אני מגריל תמורה אקראית על n איברים בהתפלגות אחידה

1. מה הסיכוי ששני איברים מסומנים יהיו באותו מעגל
2. מה הסיכוי ש-k איברים מסומנים יהיו באותו מעגל
3. מה הסיכוי ש-k איברים מוסמנים יהיו כולם במעגלים שונים

חידה 4

צפרדע עומדת על ציר המספרים בנקודה k שלמה בין 0 ל-100, בכל שלב היא קופצת בהסתברות שווה מספר אחד שמאלה או מספר אחד ימינה. כתלות ב-k מה הסיכוי שהיא תגיע ל-100 לפני שהיא תגיע ל-0.

חידה 5

אני מקבל מספר x בין 0 ל-1, בכל שלב אנחנו מעדכנים את x בצורה הבאה: אם x קטן או שווה לחצי בהסתברות חצי הוא יהפוך להיות 0 ואחרת יעבור להיות 2x, אם x גדול מחצי בהסתברות חצי הוא יהפוך להיות 1 ואחרת יעבור להיות 2x-1. מה הסיכוי שהתהליך יסתיים ב-1

חידה 6

אני מגריל p בין 0 ל-1 בהתפלגות אחידה, אני משתמש ב-p הזה כדי להגריל משתנה בינומי $X\sim Bin(100,p)$ מה הסיכוי ש-$X=37$.

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

חידה 12

1. האם יכולים להיות שני משתנים מקריים שמתפלגים אחיד בקטע [0, 1] והסכום שלהם הוא קבוע?
2. האם יכולים להיות שלושה משתנים מקריים שמתפלגים אחיד בקטע [0, 1] והסכום שלהם הוא קבוע?

אלגוריתמיקה

חידה 1

נתון מערך של מספרים, צריך למצוא את תת הסכום הכי גדול שלא מכיל אף שני מספרים סמוכים

חידה 2

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

חידה 3

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

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

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

חידה 4

יש לי מערך שיותר מחצי מאיברים בו שווים זה לזה (כלומר קיים רוב), איך מוצאים את הרוב ב-O(n)? איך עושים את זה ב-O(1) זיכרון?

חידה 5

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