سوالات مربوط به ریاضی گسسته - لطفا کمک کنید

[mahboob_tr]

با سلام و عرض ادب
به چند روش می توان اعداد 1 تا 10 را در دو ردیف 5 تایی زیر هم قرار داد به طوری که اعداد هر ستون و هر سطر به ترتیب صعودی مرتب باشند ؟

[davy jones]

با سلام و عرض ادب
به چند روش می توان اعداد 1 تا 10 را در دو ردیف 5 تایی زیر هم قرار داد به طوری که اعداد هر ستون و هر سطر به ترتیب صعودی مرتب باشند ؟

من و یکی از دوستام روی این سوال خیلی فکر کردیم.
اما به نتیجه امیدوارکننده ای نرسیدیم.
تنها چیزی که فهمیدیم اینه که جواب مساله رو اگه به صورت استقرائی نگاه کنیم با سری فیبوناچی ارتباط داره.

[mahboob_tr]

بابا به دادم برسيد

يه استاد دانشگاهي ؛ پرفسوري ؛ كسي رو پيدا كنيد اين مسئله رو حل كنه

ديگه دارم ناميد ميشم

[mahboob_tr]

من این سوال رو از کنکور کارشناسی ارشد کامپیوتر آوردم .

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

اگه می تونید یه حرکت جهادی یا انتهاری انجام بدید و جواب رو پیدا کنید

واسه بدست آوردن این مسئله سه کتاب خوندم و کلی مطلب یاد گرفتم


ولی دیگه تحمل ندارم

[davy jones]

خب مطالبی رو که یاد گرفتی به ما هم بگو شاید به دردمون خورد.

[billy_director]

جوابی که من برای مساله حدس می زنم، ترکیب 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 رقم باقی می ماند که آنها را تنها به یک طریق می توان در سطر باقی مانده چید.

[billy_director]

اصلاحیه:
1-تعداد به دست آمده را بر دو باید تقسیم نمود. زیرا مثلا دو 4567 و 2389 در واقع یکی هستند که یکیشان برای بالا و دیگری برای پایین انتخاب می شود.
2-به جز دو تر کیب 1357 و 2468 ترکیب دیگری نیافتم که بتواند هم در بالا و هم درپایین قرار گیرد.
3-با این حساب جواب مساله ، ترکیب 4 از 8 است تقسیم بر دو +1. البته فعلا!!

[billy_director]

اصلاحیه بعدی: حدس جدیدم!! این است که ترکیباتی که همزمان دارای ارقام 2و3 و یا 4و5 و یا 6و7 و یا 8و9 باشد، تنها می تواند بالا یا پایین قرار گیرد و دیگر ترکیبات می توانند هم بالا و هم پایین قرار گیرند. مثلا 2379 فقط می تواند بالا قرار گیرد و اگر پایین بیاید مساله جواب ندارد.
ان شاء الله فردا محاسباتش را انجام میدهم

[billy_director]

اثبات حدس بالا:
اگر رشته شامل 2و3 باشد، اگر بخواهد در پایین قرار گیرد، حتما باید F و G را پر کنند. در نتیجه B را نمی توان پر کرد. پس اگر رشته ای بخواهد هم در بالا قرار گیرد و هم در پایین، اولین رقمش یا 2 است یا 3 و دقیقا شامل یکی از این دو تا ست.(بدیهی است که نمی تواند شامل هیچ یک نباشد.)
اگر رشته شامل 4و5 باشد، اگر بخواهد در پایین قرار گیرد، حتما باید G وH را پر کنند.(جایگاه F توسط 2 و یا 3 پر شده است) در نتیجه C را نمی توان پر کرد. پس اگر رشته ای هم در بالا قرار گیرد و هم در پایین، دومین رقمش یا 4 است یا 5 و دقیقا شامل یکی از این دو تا ست. (بدیهی است که نمی تواند شامل هیچ یک نباشد)
به همین ترتیب می توان اثبات را در مورد ارقام 8و9 و سپس ارقام 6و7 ادامه داد.(اگر بخواهند همراه هم در بالا قرارگیرند به تناقض می رسیم)

[billy_director]

و اما محاسبات:
کل رشته های 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