خانه
گاما
تو بپرس، بقیه بهت جواب میدن!

حداقل حرکت برای مرتب‌سازی سکه‌های ترکیبیات

ترکیبیات: 10 سکه با طرح P و 10 سکه با طرح N به صورت NP...PNP مرتب شده‌اند. یک حرکت عبارت است از جابجای دو سکه متوالی. حداقل حرکت‌های لازم برای اینکه همه سکه‌های P به یک گوشه و همه سکه‌های N به گوشی دیگر بروند، مانند NN...NPP...P چند است؟

ویرایش شده 1 آبان 20:34
0
109
جواب درست

در کل یعنی 20 سکه داریم؛ یعنی 20 جایگاه. به هر کدام یک از این جایگاه‌ها، از چپ به راست، یک شماره می‌دهیم از 1 تا 20. جمع شماره جایگاه‌های N برابرست با 100=19+17+...+3+1. جمع شماره جایگاه‌های N پس از جابجایی برابر است با 55=10+9+...+3+2+1. شماره جایگاه‌ها را از هم کم کنیم: 100-55=45 پس حداقل 45 حرکت نیاز است که جایگاه Nها عوض شود و به چپ بیاید.

1
1405/08/1