נתונה הבעיה האלגוריתמית הבאה: הקלט הוא \(m\) מערכים בגודל \(k\) כל אחד, כאשר כל אחד מ-\(m\) המערכים מכיל תמורה של המספרים \(1, \dots, k\). הפלט הוא \(m\) המערכים כשכל אחד מהם ממוין. א. מה מספר הקלטים האפשריים לבעיה? ב. הוכיחו שלא ייתכן כי לבעיה זו יש אלגוריתם שעל מחצית מהקלטים מבצע \(\Theta(mk)\) השוואות (ותמיד מחזיר פלט כנדרש). הדרכה: בסעיף ב' ניתן להשתמש בעובדה שגובהו של עץ בינארי בעל \(n\) עלים הוא לפחות \(\lg n\).