با سلام و عرض ادب ;)
به چند روش می توان اعداد 1 تا 10 را در دو ردیف 5 تایی زیر هم قرار داد به طوری که اعداد هر ستون و هر سطر به ترتیب صعودی مرتب باشند ؟
Printable View
با سلام و عرض ادب ;)
به چند روش می توان اعداد 1 تا 10 را در دو ردیف 5 تایی زیر هم قرار داد به طوری که اعداد هر ستون و هر سطر به ترتیب صعودی مرتب باشند ؟
من و یکی از دوستام روی این سوال خیلی فکر کردیم.:10:نقل قول:
اما به نتیجه امیدوارکننده ای نرسیدیم.:41:
تنها چیزی که فهمیدیم اینه که جواب مساله رو اگه به صورت استقرائی نگاه کنیم با سری فیبوناچی ارتباط داره.:46:
بابا به دادم برسيد :19:
يه استاد دانشگاهي ؛ پرفسوري ؛ كسي رو پيدا كنيد اين مسئله رو حل كنه :2:
ديگه دارم ناميد ميشم :41:
من این سوال رو از کنکور کارشناسی ارشد کامپیوتر آوردم .
دیگه حتی شبها کابوس این مسئله رو می بینم
اگه می تونید یه حرکت جهادی یا انتهاری انجام بدید و جواب رو پیدا کنید
واسه بدست آوردن این مسئله سه کتاب خوندم و کلی مطلب یاد گرفتم
ولی دیگه تحمل ندارم
خب مطالبی رو که یاد گرفتی به ما هم بگو شاید به دردمون خورد.
جوابی که من برای مساله حدس می زنم، ترکیب 4 از 8 است.
فرض کنید که اعداد را به ترتیب از چپ به راست می چینید.
A B C D E
F G H I J
رقم 1 باید در A و رقم 10 باید در J بنشیند. بدین ترتیب 8 جایگاه داریم و 8 رقم . 4 جایگاه در بالا و4 جایگاه در پایین. از ارقام باقیمانده 4 تا را انتخاب می کنیم.
1-این ارقام چه بخواهند در بالا قرار بگیرند و چه بخواهند در پایین قرار بگیرند ،بایستی صعودی باشند. پس تنها به یک طریق مرتب می شوند.
2- چنانچه مساله تنها یک سطر داشت ، هر ترکیب می توانست در سطر بالا یا پایین قرار گیرد. اثبا تش سخت نیست.
3- حالا که مساله دو سطری است (هر ستون باید صعودی باشد)، هر ترکیبی نمی تواند در بالا یا پایین قرار گیرد. مثلا 4567 در بالا می تواند قرار گیرد اما اگر در پایین قرار گیرد مساله جواب ندارد(می توانید امتحان کنید). در نتیجه جای هر ترکیب 4 تایی یا بالا است یا پایین.(برای این جمله ام اثباتی ندارم.خوشحال می شوم کسی اثبات کند یا مثال نقض بیاورد.)
4-پس از این که جای 4 رقم معلوم شد، 4 رقم باقی می ماند که آنها را تنها به یک طریق می توان در سطر باقی مانده چید.
اصلاحیه:
1-تعداد به دست آمده را بر دو باید تقسیم نمود. زیرا مثلا دو 4567 و 2389 در واقع یکی هستند که یکیشان برای بالا و دیگری برای پایین انتخاب می شود.
2-به جز دو تر کیب 1357 و 2468 ترکیب دیگری نیافتم که بتواند هم در بالا و هم درپایین قرار گیرد.
3-با این حساب جواب مساله ، ترکیب 4 از 8 است تقسیم بر دو +1. البته فعلا!!
اصلاحیه بعدی: حدس جدیدم!! این است که ترکیباتی که همزمان دارای ارقام 2و3 و یا 4و5 و یا 6و7 و یا 8و9 باشد، تنها می تواند بالا یا پایین قرار گیرد و دیگر ترکیبات می توانند هم بالا و هم پایین قرار گیرند. مثلا 2379 فقط می تواند بالا قرار گیرد و اگر پایین بیاید مساله جواب ندارد.
ان شاء الله فردا محاسباتش را انجام میدهم
اثبات حدس بالا:
اگر رشته شامل 2و3 باشد، اگر بخواهد در پایین قرار گیرد، حتما باید F و G را پر کنند. در نتیجه B را نمی توان پر کرد. پس اگر رشته ای بخواهد هم در بالا قرار گیرد و هم در پایین، اولین رقمش یا 2 است یا 3 و دقیقا شامل یکی از این دو تا ست.(بدیهی است که نمی تواند شامل هیچ یک نباشد.)
اگر رشته شامل 4و5 باشد، اگر بخواهد در پایین قرار گیرد، حتما باید G وH را پر کنند.(جایگاه F توسط 2 و یا 3 پر شده است) در نتیجه C را نمی توان پر کرد. پس اگر رشته ای هم در بالا قرار گیرد و هم در پایین، دومین رقمش یا 4 است یا 5 و دقیقا شامل یکی از این دو تا ست. (بدیهی است که نمی تواند شامل هیچ یک نباشد)
به همین ترتیب می توان اثبات را در مورد ارقام 8و9 و سپس ارقام 6و7 ادامه داد.(اگر بخواهند همراه هم در بالا قرارگیرند به تناقض می رسیم)
و اما محاسبات:
کل رشته های 4 تایی، ترکیب 4 از 8 است یعنی 70.
از این تعداد 16 رشته را می توان هم در بالا و هم در پایین قرار داد.
سوال:16 از کجا آمد؟
جواب:
از 2و 3 باید یکی را انتخاب کنیم( به دو طریق) .
از 4و 5 باید یکی را انتخاب کنیم( به دو طریق).
از 6و 7 باید یکی را انتخاب کنیم( به دو طریق).
از 8و 9 باید یکی را انتخاب کنیم( به دو طریق)
مجموعا از 2 به توان 4 طریق، عدد چهار رقمی ساختیم که همزمان دارای ارقام 2و3 و یا 4و5 و یا 6و7 و یا 8و9 نیست، پس می تواند در بالا یا پایین قرار گیرد.
پس می ماند 54 رشته که یا در بالا قرار میگیرند یا در پایین وهمانطور که قبلا گفتم دو به دو متناظرند( مثلا دو 4567 و 2389 در واقع یکی هستند.) پس این 54 رشته را بر دو تقسیم می کنیم. می شود 27.
جواب نهایی:
27+16=43
امروز به کمک یکی از دوستانم برنامه ای نوشته شد که صحت حواب را بررسی کنم. در کمال تعجب جواب 42 در آمد. بعد از یکی دو ساعت بررسی دیدم که همه موارد بالا درست است،به جز اینکه 4567 و جفت متناظرش نمی توانند جواب مساله یاشند. نه در بالا و نه در پایین.
پس جواب مساله 42 است.
با سلامنقل قول:
در صورت امکان، لطف کنید و برنامه را هم بیاورید. بنده برنامه ای با میپل برای آن نوشته ام اما برنامه ی دل چسبی نیست. با تشکر از مساله ی خوبتان.
منتظرم.
موفق باشید.
7 مرداد 1389
نقل قول:
يه كد با MATLAB (با روش بازگشتي). گويا همون جواب 42 كه دوستمون گفتن درسته
فايل‌هاي MATLAB مربوطه به همراه خروجي برنامه
کد:http://www.4shared.com/file/80YIGpkZ/counter.html
سوالی که حالا من به نظرم میرسه اینه.
چه رشنه هایی نه در بالا می توانند قرار گیرند و نه در پایین ؟ منظورم اینه که برای این که رشته ای جواب مساله نباشد چه شرایطی را باید داشنه باشد؟
برای A+B تابع مشخصه تعیین کنید؟A+b(x)~
برای هریک از توابع زیر الگوریتم بازگشتی بنویسید؟
f(X,y)=x-y
g(x,y)خارج قسمت صحیح تقسیم xبرy
لطفا پاسخ این سوالات را بدهید