جدول 2000 در 2000

amir.ekhlasi

New Member
ارسال ها
364
لایک ها
183
امتیاز
0
#1
درون خانه های جدولی 2000 در 2000 اعداد 1 یا 1- قرار داده ایم. میدانیم جمع اعداد جدول نامنفی است. ثابت کنید 1000 سطر و 1000 ستون وجود دارند که مجموع اعداد در تقاطع آنها (تقاطع دو به دوی این سطر و ستونها) بیش از 1000 است.
 

fereidoon

Active Member
ارسال ها
447
لایک ها
132
امتیاز
43
#2
پاسخ : جدول 2000 در 2000

با توجه به فرض سوال,1000 را n در نظر بگيريد و سوال را بازسازي كنيد,اونوقت فرض كنيد كه مجموع اعداد جدول برابر حداقل k باشد,سپس يك جدول كوچكتر (n-1)(n-1) وجود خواهد داشت كه جمع اعداد ان k+1* است,حالا انوقت مي توان جمع كل جدول را دقيقا k كرد(زيرا يكي از 1 ها رو 1- مي كنيم)سپس با استفاده از اصل ميانگين يك ستون هست كه كمتر از جمع اعداد واقع در ان كمتر از 0 است,سپس با كمي بررسي اين ستون و ان زير جدول(n-1)(n-1) مسئله حل است.
 

mojtabaaa1373

Active Member
ارسال ها
362
لایک ها
74
امتیاز
28
#3
پاسخ : جدول 2000 در 2000

یه راه دیگه هم جا به جا کردن سطر ها و ستون هاست اول ثابت میشه که این کار قابل انجامه بعد هم از الگوریتم حریصانه استفاده کنیم مسئله حله.
 

amir.ekhlasi

New Member
ارسال ها
364
لایک ها
183
امتیاز
0
#4
پاسخ : جدول 2000 در 2000

یه راه دیگه هم جا به جا کردن سطر ها و ستون هاست اول ثابت میشه که این کار قابل انجامه بعد هم از الگوریتم حریصانه استفاده کنیم مسئله حله.
میشه بیشتر توضیح بدید.
 
بالا