مسابقهی شماره ۲۰۱
در یک پارک ۱۰۰۰۰ درخت در یک شبکهی منتظم مربعی-شکل کاشته شدهاند (یک جدول ۹۹در۹۹ را در نظر بگیرید که در هر راس جدول یک درخت کاشته شده است).
تعیین کنید حداکثر چند درخت از پارک را میتوان قطع کرد بهشرطی که: از روی هر کُندهی درخت، کُندهی هیچ درخت دیگری دیده نشود.
اگر همهٔ راسهای این شبکه از درختهای را در مربعهای کوچک دستهبندی کنیم، آنگاه از هر ۴ راس هریک از این مربعها تنها یک درخت را میتوان قطع کرد. یعنی حداکثر ۲۵۰۰ راس درخت میتوان قطع کرد. همچنین با توجه به شکل زیر میتوان دید که میتوان ۲۵۰۰ راس درخت را بهگونهای قطع کرد که کندهٔ هیچ درخت قطعشدهای از کندهٔ درخت قطعشدهٔ دیگر دیده نشود. برای این کار از سطر اول، یکیدرمیان درختها را قطع میکنیم، از سطر سوم همینطور و یکیدرمیان از سطرها ۵۰ درخت قطع میشود تا سطر نودونهم.