به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+5 امتیاز
129 بازدید
در دبیرستان توسط Mohammadamin (750 امتیاز)

ما ۱۰ تاس ۱۲ وجهی یکسان داریم و میخواهیم انهارا در چهار جعبه یکسان قرار دهیم بطوریکه هیچ جعبه ای خالی نباشد. به چند روش می توان این کار را انجام داد؟ ترتیب قرار گرفتن تاس ها در جعبه ها و ترتیب قرار گرفتن جعبه ها مهم نیست اما شماره وجوهی که در جعبه ها دیده می شوند مهم است.

1 پاسخ

+1 امتیاز
توسط AmirHosein (9,971 امتیاز)
ویرایش شده توسط AmirHosein

پرسش شما هم‌ارز است با این پرسش که چند مجموعهٔ چهارعضوی (مجموعه ترتیب ندارد) از عددهای در مبنای ۱۲ داریم که جمع تعداد رقم‌های این ۴ عدد برابر ۱۰ شود و رقم‌های این عددها از کوچک به بزرگ نوشته شده‌باشند. ابتدا ۱۰ شیء داریم که در ۴ جایگاه می‌خواهیم پخش توزیع کنیم طوری که جعبه‌ای خالی نباشد. اینکه تعداد تاس‌ها در جعبه‌ای فرق کند نتیجهٔ خروجی یعنی ثبت چهار عدد در مبنای ۱۲ که جمع تعداد رقم‌های این ۴ عدد ۱۰ شود تغییر ایجاد می‌کند (تعداد تاس‌ها در هر جعبه تعداد رقم‌های عددها را تعیین می‌کند). نوجه کنید که ترتیب مهم نیست پس برای شمردن و احتناب از تکرار حالت‌ها با جایگشت، جایگاه‌ها را بر اساس دارای بیشترین تعداد تاس بودن مرتب می‌کنیم (حالت‌هایی که جعبهٔ اول ۴ تا و جعبهٔ دوم ۲ تا تاس و بالعکس با این روش یک بار شمرده می‌شوند). پس پخش کردن این تاس‌ها به تعداد زیر، حالت متفاوت به ما می‌دهد.

$$\sum_{i_1=1}^{10}\sum_{i_2=1}^{\min(10-i_1,i_1-1)}\sum_{i_3=1}^{\min(10-(i_1+i_2),i_2-1)}\sum_{i_4=1}^{\min(10-(i_1+i_2+i_3),i_3-1)}1$$

فعلا ۱ گذاشته‌ایم چون تعداد حالت‌های متفاوت نسبت به تعداد تاس‌ها در جعبه‌ها را شمرده‌ایم (توجه کنید چون تاس‌ها از هم تفاوتی ندارند و ترتیبی لحاظ نیست پس دیگر $\binom{n}{m}$ نمی‌آوریم). اما اکنون یک گام بیشتر برویم بعد از انتخاب تعداد تاس (رقم) در هر جایگاه تعداد عددهایی که با ۱۲ عدد و با آن تعداد رقم‌ها و به ترتیب بزرگتری چیده‌شده می‌توان ساخت را باید بیاوریم. پس به جای عدد ۱ در جمع بالا باید عبارت زیر را قرار دهیم. این عبارت ضرب چهار عبارت است چون عددهای چهار جایگاه (جعبه) از هم مستقل (ناوابسته) اند پس تعداد حالت‌های هر یک در هم ضرب می‌شود.

$$\prod_{j=1}^4 \Big(\sum_{k_1=1}^{12}\sum_{k_2=1}^{k_1}\sum_{k_3=1}^{k_2}\cdots\sum_{k_{i_j}=1}^{k_{i_j-1}}1 \Big)$$

تعداد جمع‌ها برابر با تعداد رقم‌های انتخاب شده‌است. فرمول کلی برابر فرمول زیر می‌شود.

$$\sum_{i_1=1}^{10}\sum_{i_2=1}^{\min(10-i_1,i_1-1)}\sum_{i_3=1}^{\min(10-(i_1+i_2),i_2-1)}\sum_{i_4=1}^{\min(10-(i_1+i_2+i_3),i_3-1)}\Big(\prod_{j=1}^4 \Big(\sum_{k_1=1}^{12}\sum_{k_2=1}^{k_1}\sum_{k_3=1}^{k_2}\cdots\sum_{k_{i_j}=1}^{k_{i_j-1}}1 \Big)\Big)$$

توجه کنید که تعداد جمع‌های قسمت داخلی متغیر است و این یک مقدار برنامه‌نویسی را سخت می‌کند. به جای استفاده از ایدهٔ نوشتن یک جمع به آن شکل برای شمردن تعداد عددهای دارای یک سری تعداد رقم و رقم‌هایش به طور یکنوا (نه الزاما اکید) چیده شده‌اند، می‌توانیم از ایدهٔ ساده‌تری استفاده کنیم. وقتی می‌خواهید یک عددِ $n$ رقمی با $N$ رقمِ ممکن بنویسید که رقم‌هایش به طور افزایشی (نه الزاما اکید) از راست به چپ باشند، تعداد این عددها از فرمول زیر که با استقراء ریاضی بر روی $n$ ثابت می‌شود بدست می‌آید.1

$$N\frac{N+1}{2}\frac{N+2}{3}\cdots\frac{N+n-1}{n}$$

پس فرمول طولانی قبلی را به شکل زیر بازنویسی می‌کنیم.

$$\sum_{i_1=1}^{10}\sum_{i_2=1}^{\min(10-i_1,i_1-1)}\sum_{i_3=1}^{\min(10-(i_1+i_2),i_2-1)}\sum_{i_4=1}^{\min(10-(i_1+i_2+i_3),i_3-1)}\Big(\prod_{j=1}^4 \Big(\prod_{r=1}^{i_j}\frac{12+r-1}{r} \Big)\Big)$$

دستور برای انجام این محاسبه در نرم‌افزار Mathematica:

Timing[Sum[Sum[Sum[Sum[Product[Product[(12+r-1)/r,{r,1,Subscript[i, j]}],{j,1,4}],{Subscript[i, 4],1,Min[10-(Subscript[i, 1]+Subscript[i, 2]+Subscript[i, 3]),Subscript[i, 3]-1]}],{Subscript[i, 3],1,Min[10-(Subscript[i, 1]+Subscript[i, 2]),Subscript[i, 2]-1]}],{Subscript[i, 2],1,Min[10-Subscript[i, 1],Subscript[i, 1]-1]}],{Subscript[i, 1],1,10}]]

به جای Subscript[i,1] می‌توانید i را تایپ و سپس کلید ترکیبیِ Ctrl+- یعنی کلید کنترل و کلید منها (در ردیف اعداد بالای کلیدهای حروف) را با هم، فشار دهید تا به حالت زیراندیس برود وسپس 1 را بزنید و سپس کلید فلش به سمت راست را بزنید تا از زیراندیس بیرون بیایید. من دستور محاسبه را داخل دستورِ Timing نیز گذاشتم تا زمان محاسبه را هم بگیرم. خروجی به شکل {0.,465060960} درمی‌آید که یعنی تقریبا زیرِ یک میلی‌ثانیه (هزارم ثانیه) زمان کشید تا محاسبه شود و حاصل برابر است با ۴۶۵۰۶۰۹۶۰ که عدد بزرگی است. :)


  1. می‌توانید برای یک اثبات و همینطور کُد نوشتن این ضرب در چند زبان برنامه‌نویسی به این پیوند نگاه کنید (اینجا کلیک کنید). ↩︎


حمایت مالی

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