שאלת מבחן במתמטיקה בדידה - האוניברסיטה העברית 2013 - קומבינטוריקה

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

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

פתרון: **סה"כ** דרכים לחלק 5 פריטים ל-3 מדפים: $3^5 = 243$. **תנאי 1** (מדף תחתון לא ריק): חלוקות עם מדף תחתון ריק = $2^5 = 32$. אז עם לפחות אחד בתחתון: $243 - 32 = 211$. **תנאי 2** (גבינה ולימון לא באותו מדף): נספור את המשלים — מקרים שגבינה ולימון **באותו** מדף ומדף תחתון לא ריק. גבינה ולימון באותו מדף: נבחר מדף אחד מ-3 עבור שניהם, שאר 3 פריטים בחופשיות: $3 \cdot 3^3 = 81$. מתוכם, מדף תחתון ריק: גבינה ולימון לא בתחתון (2 אפשרויות למדף שלהם), ושאר 3 פריטים גם לא בתחתון ($2^3 = 8$): $2 \cdot 8 = 16$. אז גבינה ולימון יחד ומדף תחתון לא ריק: $81 - 16 = 65$. **תשובה:** $211 - 65 = **146**$. $\blacksquare$