اول یه قضیه خیلی بدیهی رو میگم

a + b = c + d , a - b < d - c

پس داریم ab > cd اثباتش کاری نداره ولی اگه خواستی بگو زیر این پست که اونم اضافه کنم

حالا میرم سر اثبات خود سوال

Ai میشه شماره جایگاهی که i توش قرار داره مثلا تو 1243 , A4 = 3

میایم ادعا میکنیم حالتی که تو این سوال جواب میده قطعا | Ai - i | یا 1 یا 0

اثبات فرض کنیم یک حالت داریم که این خاصیت رو نداره میایم اعداد رو از یک تا 20 به ترتیب میزاریم

تا جایی که یک عدد خاصیت بالا رو نداشته باشه فرض کنید اون عدد k هست

و k تو خونه k + m هست میگیم عددی که تو خونه k +m - 1 هست حداقل k + 1 هست

با توجه به لمی که اول گفتم

k + 1 + k + m - 1 = 2k + m و k + k + m = 2k + m

چون فاصله اولیه از هم کمتره پس عدد بزرگ تری میشه که خلاف فرض مسعله هست

حالا میایم اثبات میکنیم اگه درست باشه | Ai - i | برابر 1 یا 0 جایگشت خاصیت لازم رو داره

بدیهیه اگه این شرط برقرار باشه اگه k تو جایگاه k+1 باشه k+1 تو جایگاه k هست

میایم میگیم فرض کنیم اولین بار عدد k هست که تو جایگاه k + 1 اومده میایم میگیم k و k+1 که خاصیت رو دارن

جفتشون ضربشون در جایگاهشون میشه k^2 + k

اعداد قبلشون که با فرض ما از k^2 کمتره اعداد بعدشم از k+1 ^ 2 بیشتره

پس الن باید تعداد دنباله هایی رو بیابیم که | Ai - i | برابر 1 یا 0 برقرار باشه

اینو به شکل های مختلف میشه حل کرد من دنباله بازگشتیشو مینویسم

بازگشتی رو روی اولین 2 تای مجاوری که جاشون جابجا شده مینویسیم

Bi = Bi-2 + Bi-3 +... + B0 + 1 و B1 = 1 و B0 = 1

حالا B20 که سوال خواسته اینجوری حساب میشه

B20 = B18 + B17 + B 16 ... B0 + 1

که میتونین اینو به راحتی حل کنین