ثابت کنید تمام عددهای گویا در درختِ Calkin-Wilf ظاهر می شوند.

Question

درختِ Calkin-Wilf به این شکل تعریف می‌شود که در گرهٔ شروع (ریشه) شما کسر ۱ بر روی ۱ را می‌نویسید $\frac{1}{1}$. سپس از این گره دو شاخه بیرون می‌آورید که یکی از قرار دادن جمع صورت و مخرج کسر $\frac{1}{1}$ بر روی مخرجش و دیگری از قرار دادن صورتش بر روی جمع صورت و مخرجش ساخته‌شده‌اند که می‌شوند $\frac{1+1}{1}=\frac{2}{1}$ و $\frac{1}{1+1}=\frac{1}{2}$. این کار را بر روی هر گرهٔ جدیدِ درخت‌مان پیاده می‌کنیم. یعنی اگر در گره‌ای کسرِ $\frac{m}{n}$ داریم، آنگاه از آن دو شاخهٔ جدید با مقدارهای $\frac{m+n}{n}$ و $\frac{m}{m+n}$ بیرون می‌آوریم. در زیر شکل این درخت را برای ۴ نسل می‌بینید. اکنون سوأل این است که آیا همهٔ عددهای گویا بر روی این درخت ظاهر می‌شوند؟

Comments

@MATIN_3 ساختار ارائه شده دنباله نیست بلکه یک درخت است. می‌توانید خروجی را به شکل دنباله مرتب کنید برای نمونه از بالا شروع کنید به پائین و از چپ به راست ولی نحوهٔ تعریفِ این ساختار با شکلی که دادید بر حسب یک درخت tree ارائه شده‌است نه به شکل دنباله. عنوان‌تان هم از نظر معنایی نادرست است چه بیرون پرانتز، چه داخل پرانتز! به ویرایشی که روی عنوان و متن پرسش برایتان انجام دادم نگاه کنید. درست بیان‌کردن نیمی از فهمیدن است.