مورچه و صفحه شطرنج

amir.ekhlasi

New Member
ارسال ها
364
لایک ها
183
امتیاز
0
#1
یک صفحه شطرنج داریم که از بالا و راست بی کران است. مورچه ای روی خانه سمت چپ، پایین قرار دارد. این مورچه هر دفعه میتواند به سمت بالا یا راست حرکت کند. در این صفحه نامتناهی تله وجود دارد که غیر فعال هستند. بعد از هر حرکت مورچه یکی از این تله ها فعال میشود (و بعد از آن فعال میماند). اگر مورچه روی یکی از تله های فعال شده قرار بگیرد میمیرد. ثابت کنید بسته به جای و ترتیب فعال شدن تله ها، همیشه مسیری به طول نامتناهی وجود دارد که اگر مورچه آن را بپیماید هیچوقت نمیمیرد.
 

mahanmath

New Member
ارسال ها
898
لایک ها
701
امتیاز
0
#2
پاسخ : مورچه و صفحه شطرنج

به استقرا ثابت می‌کنیم در هر مرحله می‌شه به حداقل
از خانه‌های خط
رسید .
( f(n) i تعداد خونه‌های ممنوعه زیره خط x+y=n+1 تا مرحله n)

با این کار ثابت می‌شه ,می‌شه به هر مقدار دلخواهی مسیر درست کرد که مورچه زنده بمونه ولی‌ اگه از Konig استفاده کنیم نتیجه می‌شه مسیر نامتناهی هم وجود داره .

 

mahanmath

New Member
ارسال ها
898
لایک ها
701
امتیاز
0
#3
پاسخ : مورچه و صفحه شطرنج

سوالش خیلی‌ آشناس ، می‌شه بگی‌ ماله کجا بوده ؟ ممنون . :3:
 

amir.ekhlasi

New Member
ارسال ها
364
لایک ها
183
امتیاز
0
#4
پاسخ : مورچه و صفحه شطرنج

shortlist یه سالی بود.
 
بالا