مساله ۵۸. تولد دونالد

امروز، ۱۰ ژانویه، تولد دونالد کنوث (Donald Knuth) است. دونالد میخواد کیک تولدشو ۵ تا برش (سه بعدی) بده، حداکثر تعداد قطعات کیکی که می‌تونه با این ۵ برش تولید کنه چندتاست؟

شکل کیک استوانه‌ایه. هر برش یک صفحه‌ی ۳ بعدیه، و پس از برش کیک ثابت می‌مونه و قطعات آن جابجا نمی‌شه.

(برگرفته از یکی از تمرین‌های کتاب Concrete Mathematics نوشته‌ی دونالد!)

لینک مساله در توویتر: https://twitter.com/Riazi_Cafe/status/1744974043068162548

پاسخ درست ۲۶ است.

یک نمونه برش با ۵ صفحه که فضا را ۲۶ قسمت کرده است را اینجا می‌بینید: https://www.desmos.com/3d/baf22a25f7 (چون نمایش فضای استوانه‌ای در desmos آسان نبود، مکعب کشیدم. خودتان در ذهنتان از هر طرف گسترشش دهید تا استوانه شود)

در ادامه به این می‌پردازیم که چرا فضا (و در نتیجه استوانه یا مکعب را) نمی‌توان با ۵ صفحه بیشتر از ۲۶ بخش کرد.

برای این، اول نسخه ۲ بعدی مساله را حل می‌کنیم. فرض کنید L(n) تعداد حداکثر بخش‌های صفحه با استفاده از n خط باشد. وقتی خط n ام را به صفحه اضافه می‌کنیم، خطوط قبلی را حداکثر در n-1 جا قطع می‌کند، پس حداکثر n بخش جدید به صفحه اضافه می‌کند.

پس

  • L(0) = 1
  • L(1) = L(0)+1 = 2
  • L(2) = L(1)+2 = 4
  • L(3) = L(2)+3 = 7
  • L(4) = L(3)+4 = 11

حال برای نسخه ۳ بعدی، تعداد حداکثر بخش‌های فضا با n صفحه را P(n) می‌نامیم.

وقتی صفحه n ام را به فضا اضافه می‌کنیم، تقاطع n-1 صفحه قبلی با این صفحه روی این صفحه حداکثر n-1 خط تشکیل می‌دهند. پس صفحات قبلی روی این صفحه حداکثر L(n-1) بخش ۲-بعدی ایجاد می‌کنند. هرکدام از این بخش‌های ۲ بعدی، مقطع برش یکی از بخش‌های ۳ بعدی می‌تواند باشد. پس صفحه n ام با حداکثر L(n-1) بخش ۳-بعدی از بخش‌های قبلی تقاطع دارد. پس P(n)=P(n-1)+L(n-1).

بنابراین:

  • P(0) = 1
  • P(1) = P(0) + L(0) = 2
  • P(2) = P(1) + L(1) = 4
  • P(3) = P(2) + L(2) = 8
  • P(4) = P(3) + L(3) = 15
  • P(5) = P(4) + L(4) = 26