به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+3 امتیاز
148 بازدید
در دبیرستان و دانشگاه توسط کیوان عباس زاده
ویرایش شده توسط fardina

به چند طریق می توان جدول $3 \times 10$ را با موزاییک های $1 \times 2$ پوشاند ؟

توسط Taha1381
از دنباله های بازگشتی استفاده کنیذ و سپس ان را حل کنید.

1 پاسخ

+1 امتیاز
توسط AmirHosein

یک سری تصویر پسین‌تر خواهم‌افزود.

یک مستطیل با عرض ۳ و طول ۱۰ در نظر بگیرید. از سمت چپ شروع می‌کنیم به فرش کردن آن با مستطیل‌های یک در دو. سه حالت برای ردیف آخر بیشتر وجود ندارد یا یک مستطیل افقی بالا و یک مستطیل عمودی زیرش، یا سه مستطیل افقی، یا یک مستطیل عمودی بالا و یک مستطیل افقی در زیر. حالت دوم ما را به فرش کردن مسطتیل با عرض ۳ و طول ۸ کاهش می‌دهد. حالت یکم (به تقارن حالت سوم نیز مشابه می‌شود تنها با یک تقارن) شما رو به دو حالت می‌کشاند یا اینکه یک مستطیل عمودی دیگر در کنار مستطیل عمودی پائین قرار می‌دهید و دوباره به حالت فرش کردن یک مستطیل $3\times 8$ می‌‌رویم، یا اینکه دو تا مستطیل افقی در کنار مستطیل عمودی پائین می‌گذاریم. در این صورت مجبور می‌شویم گوشهٔ $1\times 1$ بالای سمت راست را باید با یک مستطیل افقی پر کنیم. آن وقت دوباره به دو راهی پیشین می‌رسیم. در اینصورت چیزی که رُخ داده‌است این است که اگر تعداد حالت‌های فرض کردن مستطیل $3\times 2n$ با مستطیل‌های $1\times 2$ را با $f(n)$ نشان دهیم، داریم: $$f(n)=f(n-1)+2\sum_{i=1}^{n-1}f(i)$$ روشن است که دستی می‌توان دید که $f(1)=3$ و $f(2)=11$.

اگر می‌خواهید شکل فرمول ساده‌تر شود می‌توانید محاسبات زیر را انجام دهید. $$\begin{array}{l} f(n)=3f(n-1)+2\sum_{i=1}^{n-2}f(i)\\ f(n-1)=f(n-2)+2\sum_{i=1}^{n-2}f(i)\\ 2\sum_{i=1}^{n-2}f(i)=f(n-1)-f(n-2)\\ \Longrightarrow f(n)=3f(n-1)+f(n-1)-f(n-2)\\ f(n)=4f(n-1)-f(n-2) \end{array}$$ بنابراین برای رابطهٔ بازگشتی نیاز به دو مقدار آغازین هستید. می‌توانید $n=1$ و $n=2$ را بردارید یا اینکه قرارداد کنید که $f(0)=1$ و دو مقدار $n=0$ و $n=1$ را بردارید. توجه کنید که برای فرمول پیشین فقط یک مقدار آغازین نیاز داشتید، و حتما نیاز به برداشتنِ $f(0)=1$ داشتید و گرنه فرمول عدد کمتری را به شما خواهد داد. علت شهودی آن نیز دقیقا همان علت شهودیِ قرار دادنِ $\binom{m}{0}=1$ است.

خواستهٔ پرسش، $f(5)$ است که می‌توانید خودتان حساب کنید.

حمایت مالی


کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...