עריכת הדף "חידות" (פסקה)

= חידות גמדים =

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

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

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

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

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