חידות

כללי

חידה 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

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

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

חידה 7

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

חידות גמדים

חידה 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 הניחושים יהיו נכונים

מתמטיקה

חידה 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}$ לא מוגדר)

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

הסתברות

חידה 1

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

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

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

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

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

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

חידה 2

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

אלגוריתמיקה

חידה 1

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

חידה 2

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

חידה 3

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

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

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