المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۷:سوال ۱۱

سوال ۱۱

ربع اوّل صفحه مختصات را مطابق شکل به خانه‌های $۱\times۱$ تقسیم می‌کنیم. به چند طریق می‌توان اعداد ۱ تا ۱۴ را در ۱۴ تا از این خانه‌ها نوشت به طوری که شرایط زیر برقرار باشد:

• در خانه‌ی (۱٫۱) (پایین‌ترین و سمت چپ‌ترین خانه) عدد ۱ نوشته شده باشد.

• اگر در خانه‌ای عددی نوشته شده بود، دقیقاً در یکی از دو خانه‌ی پایینی یا سمت چپی آن خانه، عددی نوشته شده باشد.

• اگر در خانه‌ی ($x,y$) یعنی خانه‌ی سطر $x$اُم و ستون $y$اُم، عدد $۱ \lt i$ نوشته شده بود، هر یک از اعداد ۱ تا $i-1$، در خانه‌ای مثل ($x',y'$) قرار داشته باشند که $۱\le x' \le x$ و $۱\le y' \le y$.

  1. ۸۱۹۲
  2. ۱۶۳۸۴
  3. ۲۴۵۷۵
  4. ۲۴۵۷۶
  5. هیچ‌کدام

پاسخ

گزینه‌ی (۱) درست است.

برای گذاشتن عدد 1 فقط یک راه داریم. برای گذاشتن عدد 2 دو انتخاب خواهیم داشت یکی بالای خانه اول و یکی سمت راست آن. بعد از قرار دادن عدد 2 در یکی از این دو خانه برای قرار دادن عدد 3 نیز 2 انتخاب داریم چرا که اگر عدد دو را در خانه $(2,1)$ قرار داده باشیم دیگر 3 در خانه $(1,2)$ نمی‌تواند قرار بگیرد و مجبور است در یکی از دو خان$(2,2)$ یا $(3,1)$ قرار بگیرد. در نتیجه برای هر کدام از اعداد به جز یک دو حالت انتخاب داریم و به این ترتیب جواب مورد نظر 2 به توان 13 خواهد بود که گزینه الف است.


ابزار صفحه