به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+3 امتیاز
104 بازدید
در دبیرستان توسط mahdiahmadileedari (958 امتیاز)
ویرایش شده توسط AmirHosein

پرسش زیر در بخش هوش و استعداد تحصیلی ششم مطرح شده‌است.

با استفاده از رقم‌های ۱ تا ۸ دو عدد چهاررقمی می‌نویسیم که هیچ رقمی بیشتر از یک بار به کار گرفته نشده‌باشد و همینطور جمع این دو عدد حداقل ممکن باشد. در این صورت جمع این دو عدد کدام است؟

  1. ۲۴۶۸
  2. ۳۲۷۵
  3. ۴۷۲۴
  4. ۳۸۲۵

2 پاسخ

+3 امتیاز
توسط mdardah (1,283 امتیاز)
انتخاب شده توسط mahdiahmadileedari
 
بهترین پاسخ

بنام خدا.دوعدد چهار رقمی وقتی باهم جمع می شود باید رقم هزارگان ٱنها دارای کمترین مقدارباشدبنابراین رقم هزار گان یکی از اعداد عدد 1 ورقم هزارگان دیگر عدد 2 می باشد به همین ترتیب رقم صدگان یکی عدد 3 ودیگری عدد4 باید باشد.رقم دهگان یکی 5 ودیگری عدد6 وبالاخره یکان یکی 7 ودیگری 8 باید باشد.مثلا ٱن دوعدد بصورت 1357 و 2468 میباشد البته جای رقم یکان یا دهگان یا صدگان ویا هزارگان را در دوعدد میتوان عوض کرداگر این دوعدد را باهم باهم جمع کنیم $1357+2468=3825$ وجواب (د) درست است

+1 امتیاز
توسط AmirHosein (13,308 امتیاز)

پاسخی که @mdardah داده‌اند دقیقا پاسخی است که مدنظر سازندهٔ پرسش بوده‌است. ولی در کل برای افرادی که علاقه به روش‌های گوناگون دارند، یک روش ممکن بازنویسیِ پرسش به شکل یک برنامه‌نویسی صحیح خطی (linear integer programming) که در واقع بهتر است بگوئیم بهینه‌سازی صحیح خطی است. سپس از الگوریتم‌های ارائه شده برای حل چنین مدل‌هایی می‌توانید استفاده کنید. در اینجا تنها یکی از حالت‌های ممکن برای این بازنویسی را اشاره می‌کنیم. و تأکید می‌کنیم که این روش بهترین روش نیست!

دو عدد مورد نظر را می‌توانیم به شکل روبرو بنویسیم.

\begin{align} y_1 &= 1000x_4+100x_3+10x_2+x_1\\ y_2 &= 1000x_8+100x_7+10x_6+x_5 \end{align}

که $x_i$ها رقم‌های این عددها هستند. پس پرسش بهینه‌سازی‌مان به شکل زیر در می‌آید، توجه کنید که می‌خواهیم $y_1+y_2$ کمینه شود که تابع هدف می‌شود.

$$ \begin{array}{l} \min\qquad 1000x_8+1000x_4+100x_7+100x_3+10x_6+10x_2+x_5+x_1\\ \text{s.t. }\qquad\begin{cases} x_1,\cdots,x_8\in\lbrace 1,2,\cdots,8\rbrace\\ x_i\neq x_j\;:\;\forall 1\leq i\lneqq j\leq 8 \end{cases} \end{array} $$

توجه کنید که تابع هدف خطی است. می‌ماند اینکه شرایط نامساوی را به شکل بزرگتریامساوی یا کوچکتریامساوی بازنویسی کنیم. توجه کنید که شرطِ $u\neq v$ را می‌توان به شکلِ «وَ»یِ دو شرط زیر نوشت.

\begin{array}{l} u-v\leq -\varepsilon+Ma\\ u-v\geq\varepsilon-(1-a)M \end{array}

که $\varepsilon$ را باید عدد مثبت خیلی کوچکی انتخاب کنید که در اینجا که اختلاف دو عدد ممکن (دو رقم) از یک واحد کمتر نمی‌شود مثلا نیم مقدار مناسبی است و $M$ نیز باید عدد بزرگی باشد که در اینجا که رقم‌ها حداکثر ۸ هستند عدد ۱۰ بد نیست. پس $\varepsilon$ و $M$ را خودمان انتخاب می‌کنیم و ثابت هستند ولی $a$ یک متغیر بولی جدید است که به پرسش افزوده‌ایم به این نوع متغیرها «متغیرهای کمکی» می‌گوئيم. اضافه شدنشان می‌تواند جستجو برای پاسخ را پرهزینه‌تر کند (از نظر زمان و پیچیدگی و غیره) ولی هزینه‌ای است که برای تبدیل شرط‌های بهینه‌سازی در حال پرداخت هستیم. پس اکنون شکل زیر یک هم‌ارز از بین هم‌ارزهای ممکن برای پرسش اصلی این پست ولی در چهارچوب بهینه‌سازی صحیح خطی است.

$$ \begin{array}{l} \min\qquad 1000x_8+1000x_4+100x_7+100x_3+10x_6+10x_2+x_5+x_1\\ \text{s.t. }\qquad\begin{cases} x_i-x_j+0.5-10a_{i,j}\leq 0\;:\;1\leq i\leq 7,\;i+1\leq j\leq 8\\ x_i-x_j-0.5+10-10a_{i,j}\leq 0\;:\;1\leq i\leq 7,\;i+1\leq j\leq 8\\ x_i-1\geq 0\;:\;1\leq i\leq 8\\ x_i-8\leq 0\;:\;1\leq i\leq 8\\ a_{i,j}\text{ boolean }\;:\;1\leq i\leq 7,\;i+1\leq j\leq 8\\ x_i\text{ integer }\;:\;1\leq i\leq 8 \end{cases} \end{array} $$

دستورهای آمادهٔ نرم‌افزار Maple خیلی برای حل این مسأله مناسب نیستند (دست‌کم نسخهٔ ۲۰۲۰ این‌گونه است). برای نمونه می‌توانید از دستور LPSolve از بستهٔ Optimization استفاده کنید.

st := time[real]();
LPSolve(1000*x[8] + 100*x[7] + 10*x[6] + x[5] + 1000*x[4] + 100*x[3] + 10*x[2] + x[1], {seq(seq(`<=`(x[i] - x[j] + 0.5 - 10*a[i, j], 0), j = i + 1 .. 8), i = 1 .. 7), seq(seq(0 <= ((x[i] - x[j] - 0.5) + 10) - 10*a[i, j], j = i + 1 .. 8), i = 1 .. 7), seq(1 <= x[i], i = 1 .. 8), seq(x[i] <= 8, i = 1 .. 8)}, assume = integer, binaryvariables = {seq(seq(a[i, j], j = i + 1 .. 8), i = 1 .. 7)});
time[real]() - st;

حدود ۶ و نیم ثانیه بر روی رایانه‌ای که این کد را اجرا کردم زمان برد و در آخر پیام خطای زیر را داد:

Error, (in Optimization:-LPSolve) maximal depth, 54, of branch and bound search is too small; use depthlimit option to increase depth

حتی با افزایش depthlimit تا ۳۰۰۰ نیز مشکل حل نمی‌شود. اما اگر کران بالای رقم‌ها را به جای ۸ عدد ۹ بگذاریم که در حالت پرسش ما در پاسخ تغییری ایجاد نمی‌کند، آنگاه با مقدار ۱۰۰۰ برای depthlimit به یک پاسخ می‌رسد که اتفاقا پاسخ درست نیست.

st := time[real]();
LPSolve(1000*(x[8] + x[4]) + 100*(x[7] + x[3]) + 10*(x[6] + x[2]) + x[5] + x[1], {seq(seq(`<=`(x[i] - x[j] + 0.5 - 10*a[i, j], 0), j = i + 1 .. 8), i = 1 .. 7), seq(seq(0 <= ((x[i] - x[j] - 0.5) + 10) - 10*a[i, j], j = i + 1 .. 8), i = 1 .. 7), seq(1 <= x[i], i = 1 .. 8), seq(x[i] <= 9, i = 1 .. 8)}, assume = integer, binaryvariables = {seq(seq(a[i, j], j = i + 1 .. 8), i = 1 .. 7)}, depthlimit = 1000);
time[real]() - st;

پاسخی که می‌دهد عبارت است از

$$(x_1,\cdots,x_8)=(1,3,5,6,2,7,4,8),\;y_1+y_2=4104$$

این پاسخ در شرایط مدل بهینه‌سازی‌مان صدق می‌کند ولی کمینهٔ مطلق تابع هدف نیست، لذا الگوریتم استفاده شده در یک کمینهٔ نسبی در مشبکهٔ ایجاد شده بوسیلهٔ شرط‌ها به تله افتاده‌است.

جالب‌تر اینکه اگر ضرایب تابع هدف را فاکتور بگیرید Maple در یک پاسخ نادرست دیگر به تله می‌افتد!

st := time[real]();
LPSolve(1000*(x[8] + x[4]) + 100*(x[7] + x[3]) + 10*(x[6] + x[2]) + x[5] + x[1], {seq(seq(`<=`(x[i] - x[j] + 0.5 - 10*a[i, j], 0), j = i + 1 .. 8), i = 1 .. 7), seq(seq(0 <= ((x[i] - x[j] - 0.5) + 10) - 10*a[i, j], j = i + 1 .. 8), i = 1 .. 7), seq(1 <= x[i], i = 1 .. 8), seq(x[i] <= 9, i = 1 .. 8)}, assume = integer, binaryvariables = {seq(seq(a[i, j], j = i + 1 .. 8), i = 1 .. 7)}, depthlimit = 1000);
time[real]() - st;

این بار پاسخ داده‌شده بوسیلهٔ Maple1 پاسخ زیر است.

$$(x_1,\cdots,x_8)=(1,4,6,5,2,3,7,8),\;y_1+y_2=3843$$

پس می‌بینید که Maple به سبکی که الآن برنامه‌نویسی برای این نوع بهینه‌سازی شده‌است در پاسخ‌های موضعی می‌تواند به تله بیفتد. ولی پاسخ @mdardah هم در شرایط مدل بهینه‌سازی صدق می‌کند و هم کمینهٔ اکید است پس پاسخ این مدل بهینه‌سازی نیز همان است. می‌توانید به یک کتاب پیرامون بهینه‌سازی صحیح خطی مراجعه کنید و یکی از الگوریتم‌های معرفی شده در آنجا را خودتان بر روی این مدل پیاده کنید تا به پاسخ اصلی برسید. ولی دوباره تأکید می‌کنم که استفاده از بهینه‌سازی صحیح خطی بهترین راه برای این پرسش نیست، صرفا یکی از راه‌های ممکن است.


حمایت مالی

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