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