به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+2 امتیاز
171 بازدید
در دبیرستان توسط Elyas1 (4,206 امتیاز)
ویرایش شده توسط AmirHosein

در کلاس ترکیبیات، آوا همه زیرمجموعه‌های ناتهی مجموعه $\lbrace 1,2,\dots,1397\rbrace$ را بر روی تخته نوشت. وی در ادامه به جای هر زیرمجموعه میانگین اعضای آن را قرار می‌دهد. میانگین اعداد نوشته شده بر روی تخته چند است؟

مرجع: المپیاد ریاضی دوره دوم متوسطه، مرحلهٔ اول، 37 امین دوره

1 پاسخ

+2 امتیاز
توسط AmirHosein (18,465 امتیاز)
ویرایش شده توسط AmirHosein
 
بهترین پاسخ

مجموعهٔ $P$ را عددهای طبیعیِ $\lbrace 1,2,\dots,n\rbrace$ تعریف کنید. $2^n-1$ زیرمجموعهٔ ناتهی دارد. اگر میانگینِ یک زیرمجموعه از $P$ مانند $A$ را با $\mu_A$ نمایش دهیم آنگاه عدد خواسته‌شدهٔ شما که آن را با $\mu$ نمایش دهید (بدون زیراندیس) برابر است با

$$\mu=\frac{\sum_{\emptyset\neq A\subseteq P}\mu_A}{2^n-1}$$

اما خودِ $\mu_A$ها چه هستند؟

$$\mu_A=\frac{\sum_{i\in A}i}{|A|}$$

که منظور از $|A|$ تعداد اعضایِ $A$ است. پس مثلا اگر $A=\lbrace 2,5,8\rbrace$ آنگاه

$$\mu_A=\frac{2+5+8}{3}=5$$

ولی بیایید به جای ساده کردن و گذاشتن یک عدد، یک ترکیب خطی از اعضای اصلی ولی با ضریب گویا استفاده کنیم. یعنی مثلا اگر $P=\lbrace 1,2,\dots,8\rbrace$ آنگاه به جای نوشتن ۵ بنویسید

$$\mu_A=\frac{0}{3}(1)+\frac{1}{3}(2)+\frac{0}{3}(3)+\frac{0}{3}(4)+\frac{1}{3}(5)+\frac{0}{3}(6)+\frac{0}{3}(7)+\frac{1}{3}(8)$$

که دقیقا یک چیز است و برابر با ۵ ولی برتریِ این نمایش در چیست؟ اکنون صورتِ کسرِ $\mu$ جمعی از عبارت‌های جبری است. پس به شکلِ

$$\mu=\frac{c_1(1)+c_2(2)+\dots+c_n(n)}{2^n-1}$$

درمی‌آید که $c_i$ جمع ضرایبِ $(i)$ در هر یک از میانگین‌های زیرمجموعه‌ای است. به عبارت بالا خوب دقت کنید. شبیه به چیزی نیست؟ اگر به جای $c_i$، از $\frac{c_i}{2^n-1}$ در پشت $(i)$ها استفاده کنیم و مخرج قبلی را که الآن در ضرایب اعمال شده‌است را کنار بیندازیم، شبیه به میانگین وزن‌دار نیست؟ اگر برای چند $n$ کوچک مانند $n=1,2,3,4$ پیش‌تر پرسش را آزموده باشید باید حدس زده باشید که میانگینِ پایانی یعنی $\mu$ برابر با میانگینِ خود $(i)$ها می‌شود یعنی میانگین $P$. چه زمانی میانگین زون‌دارِ یک سری داده با میانگین معمولی‌شان یکی می‌شد؟ پاسخ کلی‌ای ندارد ولی یک حالت ویژه این است که همهٔ وزن‌ها یکسان باشند. اگر هر عضوی به میزان یکسانی سهم داشته‌باشد آنگاه میانگین‌شان با میانگین بدون وزن یکسان می‌شود. پس بیایید ببینیم آیا همچین حالتی رخ داده‌است؟

یک $i$ را ثابت انتخاب کنید. اکنون می‌خواهیم ضریبش در تک تک میانگی‌های زیرمجموعه‌ای را جمع کنیم. در چند زیرمجموعهٔ تک‌عضوی نمایان می‌شود؟ $\binom{1}{1}$ (یک عدد داریم که می‌خواهیم همان یک عدد را هم انتخاب کنیم). در چند زیرمجموعهٔ دوعضوی نمایان می‌شود؟ $\binom{1}{1}\binom{n-1}{1}$ (یک عدد داریم که می‌خواهیم انتخاب شود. سپس از $n-1$ عدد باقیمانده یکی می‌خواهیم انتخاب کنیم. و توجه کنید که در مجموعه ترتیب مهم نیست و همینطور تکرار نداریم). در چند زیرمجموعهٔ ۳ عضوی نمایان می‌شود $\frac{\binom{1}{1}\binom{n-1}{1}\binom{n-2}{1}}{2!}$ (توجه کنید که دو عضو بعدی به $2!$ جابجایی دارند که نباید متمایز شمرده شوند). به همین شکل در $\frac{\binom{1}{1}\binom{n-1}{1}\cdots\binom{n-m}{1}}{(m-1)!}$ زیرمجموعهٔ $m$ عضوی که $1\leq m\leq n$، نمایان می‌شود.

چرا تعداد نمایان شدنش در زیرمجموعه‌های $m$عضوی را شمردیم؟ چون ضریبش در تمام میانگین‌های زیرمجموعه‌ای که تعداد اعضای یکسانی دارند برابر است با $\frac{1}{m}$. پس باید اکنون برایتان روشن باشد که مقدارِ $c_i$ چه می‌شود.

$$c_i=\frac{\binom{1}{1}}{1}+\frac{\binom{1}{1}\binom{n-1}{1}}{2}+\frac{\binom{1}{1}\binom{n-1}{1}\binom{n-2}{1}}{3\times 2!}+\dots+\frac{\binom{1}{1}\binom{n-1}{1}\cdots\binom{1}{1}}{n\times (n-1)!}$$

و چون سمت راست عبارت بالا مستقل از $i$ است، ثابت شد که مقدار $c_i$ها همگی برابر است. و این نتیجه‌ای که می‌خواستیم را کامل می‌کند.

$$\mu=\frac{1+2+\dots+n}{n}=\frac{n+1}{2}$$
توسط pourya-azary (93 امتیاز)
+1
با عرض سلام و خدا قوت.
اثبات بسیار زیبایی بود. در فرمول c_i
تو مخرج کسر آخر، به جای !n باید !(n-1) باشه که حین تایپ از قلم افتاده.
توسط AmirHosein (18,465 امتیاز)
@pourya-azary با سپاس، تصحیح شد.
توسط pourya-azary (93 امتیاز)
خواهش میکنم
توسط pourya-azary (93 امتیاز)
با عرض سلام و خدا قوت

با اینکه جواب سوال مستقل از مقدار $ c_{i} $   است ولی حالا که اینجا مطرح شده گفتم مقدارش را محاسبه کنم.

$\mu=\frac{c_1(1)+c_2(2)+\dots+c_n(n)}{2^n-1}= \frac{ \sum  c_{i} \big(i\big)  }{ 2^{n}-1 } = \frac{[ \binom{n-1}{0} \frac{1}{1} + \binom{n-1}{1} \frac{1}{2}+...+ \binom{n-1}{n-1} \frac{1}{n}] \sum  \big(i\big)      }{ 2^{n}-1 }= \frac{[ \binom{n-1}{0} \frac{n}{1} . \frac{1}{n}+ \binom{n-1}{1} \frac{n}{2} . \frac{1}{n}+...+ \binom{n-1}{n-1} \frac{n}{n} . \frac{1}{n}] \sum  \big(i\big)       }{ 2^{n}-1 }= \frac{[ \binom{n}{1} \frac{1}{n}+ \binom{n}{2} \frac{1}{n} +.... \binom{n}{n} \frac{1}{n} ] \sum  \big(i\big)     }{ 2^{n}-1 }= \frac{[ \frac{1}{n}.( 2^{n}-1)] \frac{n.(n+1)}{2}   }{ 2^{n}-1 } = \frac{n+1}{2}   $

حمایت مالی

کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...