به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+2 امتیاز
484 بازدید
در دبیرستان توسط SN (249 امتیاز)
ویرایش شده توسط AmirHosein

چرا مجموعهٔ شامل تمام زیرمجموعه‌های $[\frac{n}{2}] $-عضویِ یک مجموعهٔ $n$-عضوی، یکی از بلندترین پادزنجیرهای آن است؟

منظور از پادزنجیر یک مجموعه، مجموعه‌ای از زیرمجموعه‌های آن است که هیچ دو عضوی از آن زیرمجموعهٔ یکدیگر نشوند. برای مثال:

$$\begin{array}{l} A=\{1,2,3,4\}\\ R=\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\} \end{array}$$

که $R$ بلندترین پادزنجیر $A$ است.

مرجع: تعمیمی برای پرسش ۷ صفحهٔ ۶ کتاب ریاضی تکمیلی پایهٔ نهم (سال تحصیلی ۱۴۰۰-۱۴۰۱)، فصل اول (مجموعه‌ها)
توسط AmirHosein (18,463 امتیاز)
+1
@amir7788 برخی زیرمجموعه‌های مجموعهٔ توانی با رابطهٔ زیرمجموعه‌بودن پادزنجیر می‌شوند. این پادزنجیرها، هر یک، یک مجموعه است. یک مجموعه دارای عدد اصلی است. اگر مجموعهٔ اولیه متناهی بوده باشد، مجموعهٔ توانی نیز متناهی عضو و در نتیجه هر زیرمجموعه‌اش نیز متناهی عضو دارد. بین این عددهایی که عدداصلیِ پادزنجیرها می‌توانند باشند، یک عدد بزرگترین عددِ ممکن است. اکنون هر پادزنجیری که عدداصلی‌اش این عدد باشد را «بلندترین پادزنجیر» می‌گوئیم. هیچ ادعا یا بحثی پیرامون یکتا بودن بلندترین پادزنجیر در تعریف نیست. همانطور که در کلاسِ درس، دانش‌آموز با بیشترین نمره، می‌تواند نایکتا باشد.

من ثابت کردم که هیچ پادزنجیری با بیشتر از این تعداد عضو وجود ندارد، این خودبه‌خود یعنی هر پادزنجیری باید کمتر یا مساوی این عدد، عضو داشته‌باشد. بعد نشان دادم حداقل یک پادزنجیر با این تعداد عضو وجود دارد. چون هیچ پادزنجیری نمی‌تواند بیشتر از این عضو داشته باشد پس اگر پادزنجیر دیگری بزرگتر یا مساوی سایر پادزنجیرها عضو داشته‌باشد باید دقیقا این عدد عضو داشته‌باشد. کسی در مورد مساوی بودن خود بلندترین پادزنجیرها حرفی نمی‌زند. اکنون اینکه چند تا بلندترین پادزنجیر وجود دارد، یک پرسش دیگر است و تناقضی با این پرسش و پاسخش ندارد. برای اثبات اینکه بیشترین نمره در یک آزمون در یک کلاس ۱۹ بوده‌است نیازی نیست حتما یک نمرهٔ ۱۹ فقط در کلاس وجود داشته‌باشد، تنها چیزی که نیاز است این است که فردی با نمرهٔ بیشتر از ۱۹ نباشد و حداقل یک فرد ۱۹ گرفته‌باشد، حالا تعداد افراد با نمرهٔ ۱۹ یک مفهوم دیگر است و برابر با مفهومِ «بیشترین نمرهٔ کلاس در آزمون» نیست.
توسط amir7788 (2,708 امتیاز)
ویرایش شده توسط amir7788
+1
@AmirHoseinیکتایی فقط برای اینکه بگویم راه حل شما با این فرض درست می باشه.عنوان کردم.
برای یک مجموعه 3 عضوی، بلندترین پاد زنجیر دو تاست اما صورت مسئله فقط برای یکی درست است. نه برای هر کدام. این مثال نقضی برای مسئله می باشه. برای همین صورت سوال باید اصلاح بشه تا جواب شما هم  برای آن درست شود.
توسط AmirHosein (18,463 امتیاز)
+3
@amir7788 متن پرسش را دوباره خواندم، جملهٔ نخستش معنای یکتایی را که می‌گوئید می‌دهد و نیاز به تصحیح دارد. یعنی می‌گوید که بلندترین پادزنجیر، همان پادزنجیری است که اشاره شده‌است، در حالیکه ممکن است یکتا نباشد، برای نمونه همان حالت $n$ فرد. این جمله الآن ویرایش شد.
«چرا بلندترین پادزنجیر یک مجموعهٔ $n$-عضوی، شامل تمام زیر مجموعه‌های $[\frac{n}{2}] $ آن است؟» --> «چرا مجموعهٔ شامل تمام زیر مجموعه‌های $[\frac{n}{2}] $-عضویِ یک مجموعهٔ $n$-عضوی، یکی از بلندترین پادزنجیرهای آن است؟»
توسط amir7788 (2,708 امتیاز)
@AmirHosein با ویرایش شما خیلی بهتر شد حتی به جای « یکی از بلندترین پاد زنجیره‌ای آن است؟» می توانید فقط به عبارت ساده تر «بلندترین پاد زنجیر است؟» اشاره کنید.
توسط SN (249 امتیاز)
+1
@amir7788 ، جمله اول سوالم همان طور که اشاره کردید ، ممکن بود اشاره به مجموعه یکتایی قلمداد شود ، مرسی از توجهتون و ممنون از AmirHosein@ که ویرایش کردند .

1 پاسخ

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

نکتهٔ ۱: دو مجموعهٔ متناهی با تعداد اعضای یکسان، اگر یکی زیرمجموعهٔ دیگری باشد، آنگاه در واقع این دو مجموعه با هم برابر هستند. (اثباتش باید برایتان بدیهی باشد اما اگر نمی‌توانید انجام دهید بپرسید).

نکتهٔ ۲: بیشینهٔ $\binom{n}{k}$ که $k$ بتواند از بین عددهای ۰ و ۱ و ... و $n$ گزیده‌شود (انتخاب شود)، زمانی رخ می‌دهد که $k=[\frac{n}{2}]$ (اگر $n$ فرد باشد، این بیشینه برای دو عدد رخ می‌دهد، عدد دوم $k=[\frac{n}{2}]+1$ است که در واقع برابر با $n-k$ برای $k$-ِ پیشین است). برای اثبات به پیوند زیر نگاه کنید.

https://math.irancircle.com/24773/#a24874

اکنون اثبات اینکه گردایهٔ تمام زیرمجموعه‌های $k$-عضویِ $A$ که $k=[\frac{n}{2}]$ یک پادزنجیر با بیشترین تعداد عضو ممکن نسبت به رابطهٔ زیرمجموعه‌بودن در فضای مرتبِ جزئیِ $(P(A),\subseteq)$ می‌سازد (که منظور از $P(A)$ مجموعهٔ توانیِ $A$ است).

اثبات: برای اثبات باید چه کار کرد؟ ابتدا باید نشان داد که گردایه‌ای که اشاره کردیم یک پادزنجیر است. پس از این گام شروع می‌کنیم. نام این گردایه را $B$ بگذارید. توجه کنید که هر عضو از این گردایه مجموعه‌ای $k$ عضوی هستند، اگر قرار باشد $B$ پادزنجیر نباشد یعنی دست‌کم دو عضو در $B$ هست که یکی زیرمجموعهٔ دیگری است، نه؟ اما با توجه به نکتهٔ ۱ بالا دو مجموعهٔ متناهی با تعداد یکسانی عضو، اگر یکی زیرمجموعهٔ دیگری باشد، آنگاه هر دو برابر هستند. پس در نتیجه هیچ دو عضوِ متمایزی در $B$ نیست که یکی زیرمجموعهٔ دیگری باشد. این اثباتِ پادزنجیر بودنِ $B$ را کامل می‌کند. توجه کنید که در این اثبات از اینکه $k$ را چه عددی انتخاب کردیم هنوز استفاده نکردیم، پس اگر $B$ را گردایهٔ زیرمجموعه‌های ۱-عضوی، یا $n$-عضوی (که فقط خود $A$ را شامل می‌شود)، یا صفرعضوی (که فقط تهی را شامل می‌شود)، یا هر عدد دیگری بین صفر و $n$ برمی‌داشتیم، می‌گرفتیم نیز باز هم یک پادزنجیر می‌داشتیم. از بین این $n+1$ گزینه برای پادزنجیر ساختن بنا به نکتهٔ ۲ بالا مشخص است که برای داشتن بیشترین تعداد عضو از بین این $n+1$ گزینه، انتخابِ $k=[\frac{n}{2}]$ بهترین است. توجه کنید که تعداد زیرمجموعه‌های $k$-عضویِ $A$ برابر با $\binom{n}{k}$ است.

اما آیا تنها پادزنجیرهای فضایِ مرتبِ جزئیِ $(P(A),\subseteq)$ این $n+1$ گزینه هستند؟ خیر. پس هنوز این مطلب که پادزنجیر معرفی‌شده‌مان بیشترین تعداد عضو ممکن را دارد کامل نشده‌است. بیایید یک پادزنجیر دلخواه برداریم و نام آن را $C$ بگذارید. این پادزنجیر می‌تواند تعدادی زیرمجوعهٔ صفرعضوی، یا یک‌عضوی، یا دوعضوی، ...، یا $n$-عضوی داشته باشد. البته مشخص است که اگر تنها یک صفرعضوی داریم که تهی است و اگر آن را برداریم دیگر نمی‌توانیم زیرمجموعهٔ دیگری از $A$ را برداریم چون تهی زیرمجموعهٔ هر عضو دیگری خواهدشد. و همین طور تنها یک زیرمجموعهٔ $n$-عضوی داریم که خود $A$ است و اگر آن را برداریم دیگر زیرمجموعهٔ دیگری نمی‌توانیم برداریم چون زیرمجموعهٔ $A$ خواهد بود. به هر حال بیایید برای هر $k$ای بین صفر تا $n$، تعداد اعضای $C$ که $k$ عضو دارند را با $C_k$ نمایش دهید (پس $C_k$ها زیرمجموعه‌هایی از $C$ هستند که اعضایشان زیرمجموعه‌هایی از $A$ هستند). توجه کنید که در بهترین حالت تعداد اعضای $C_k$ برابر با تعداد کل زیرمجموعه‌های $k$-عضوی خواهد شد. به هر حال، دوباره نکتهٔ ۲ بالا را به یاد آورید.

$$\forall k\in\lbrace 0,1,\dots,n\rbrace\;\colon\;\binom{n}{k}\leq\binom{n}{[\frac{n}{2}]}$$

به یاد آورید که دو کسر با صورت یکسان، آنی بزرگتر است که مخرجش کوچکتر باشد. پس:

$$\forall k\in\lbrace 0,1,\dots,n\rbrace\;\colon\; \frac{|C_k|}{\binom{n}{[\frac{n}{2}]}}\leq\frac{|C_k|}{\binom{n}{k}}$$

اکنون برای تمام گزینه‌های (انتخاب‌های) $k$ سمت‌های چپ نابرابریِ بالا را با هم و تمام سمت‌های راست را با هم جمع می‌کنیم. این کار یک نابرابریِ جدید با سمتِ نابرابریِ یکسان به ما خواهد داد.

$$\sum_{k=0}^n\frac{|C_k|}{\binom{n}{[\frac{n}{2}]}}\leq \sum_{k=0}^n\frac{|C_k|}{\binom{n}{k}}$$

اکنون از نابرابریِ لوبِل-یامامُتُ-مِشالکین Lubell-Yamamoto-Meshalkin کمک می‌گیریم که برای پادزنجیرها مانند $C$ می‌گوید جمع کسرهایی که در سمت راستِ نابرابریِ بالا می‌بینیم از ۱ کوچکتر یا مساوی می‌شود. برای این قضیه می‌توانید به صفحهٔ ویکی‌پدیایش نگاه بیندازید.

https://en.wikipedia.org/wiki/Lubell–Yamamoto–Meshalkin inequality

پس چون سمت راستِ نابرابری بالا از ۱ کوچکتریامساوی است، باید سمت چپ نیز از ۱ کوچکتر یا مساوی شود و خواهیم داشت؛

$$\sum_{k=0}^n\frac{|C_k|}{\binom{n}{[\frac{n}{2}]}}\leq 1$$

اکنون توجه کنید که $\binom{n}{[\frac{n}{2}]}$ یک عدد ثابت است، پس می‌توانیم آن را از جمع بیرون بکشیم.

$$\frac{\sum_{k=0}^n|C_k|}{\binom{n}{[\frac{n}{2}]}}\leq 1$$

اما جمع بالای کسر سمت چپ چیست؟ جمع تعداد اعضای صفرعضوی، و تعداد اعضای یک‌عضوی، و تعداد اعضای دوعضوی، و ... -ِ مجموعهٔ $C$ چیزی به جز تعداد همهٔ اعضایش بدون شرط روی تعداد عضوهایشان می‌شود؟ یعنی داریم $\sum_{k=0}^n|C_k|=|C|$. پس داریم

$$\frac{|C|}{\binom{n}{[\frac{n}{2}]}}\leq 1$$

و چون $\binom{n}{[\frac{n}{2}]}$ مثبت است اگر دو طرف را در این عدد ضرب کنیم، جهتِ نابرابری یکسان می‌ماند.

$$|C|\leq\binom{n}{[\frac{n}{2}]}$$

این یعنی چه؟ یعنی اینکه تعداد اعضای هر پادزنجیری در فضای $(P(A),\subseteq)$ باید از $\binom{n}{[\frac{n}{2}]}$ کوچکتر یا مساوی باشد. و این تعداد اعضای پادزنجیر معرفی‌شدهٔ ما است ^_^

توجه کنید که بخش دوم اثبات برای اینکه ثابت کند که $\binom{n}{[\frac{n}{2}]}$ کرانِ بالایی برای تعداد اعضای پادزنجیرهای مطلوب ما است کافی است ولی به تنهایی ثابت نمی‌کند که این کران بالا برابر با بیشینهٔ دقیق هم است. یعنی بدون بخش اول اثبات، نمی‌توانستیم از بخش دوم به تنهایی نتیجه بگیریم که کران بالای کوچکتری وجود ندارد و این عدد می‌تواند اتخاذ شود.

توسط amir7788 (2,708 امتیاز)
+1
@AmirHiaeinاگر بلندترین پاد زنجیر منحصر به فرد باشه این شیوه درسته. از کجا می دانید بلندترین پاد زنجیر دیگری وجود ندارد؟
توسط AmirHosein (18,463 امتیاز)
+2
@amir7788 متن گزارهٔ اثبات‌شده و متن اثباتش هیچ یک صحبتی از یکتا بودن پادزنجیر با بیشترین درازا در این مجموعهٔ جزئا مرتب نکرده‌است. و چیزی که گفتید نیز نادرست است، برای ثابت کردن اینکه عدد ادعا شده، بیشینه تعداد عضوِ ممکن در یک پادزنجیر در این ساختار است، نیازی به یکتایی چنین پادزنجیری ندارید. صرفا نیاز به یک مثال با این تعداد عضو هستید و اینکه هیچ پادزنجیری با تعداد بیشتر عضو وجود نداشته‌باشد. در واقع شما بین عددهای صحیح بین صفر و $2^n$ (که $n$ تعداد عضوهای $A$ است) به دنبال عدد یکتایی هستید که بیشینهٔ ممکن برای تعداد عضوهای یک پادزنجیر در $(P(A),\subseteq)$ باشد. پس چیزی که یکتایی‌اش را می‌خواهید این عددِ صحیح است نه یک پادزنجیرِ یکتا.
در روزمره و زبان فارسی نگاه کنیم. در آزمونی بیشینهٔ نمرهٔ ممکن ۲۰ است، اینکه بیشتر از یک نفر ۲۰ بشوند با بیشینه بودن ۲۰ به عنوان نمرهٔ این آزمون تناقضی می‌سازد؟
توسط amir7788 (2,708 امتیاز)
@AmirHosein اجازه بدید با نظر شما مخالف باشم. وقتی می گویند بلندترین پاد زنجیر  یه خاصیتی دارد در زبان ریاضی مفهومش واضح است یعنی هر پاد زنجیری که بلندترین باشد. مفهومش هیچگاه این نیست که بلندترین زنجیری با این خاصیت دارد.
توسط AmirHosein (18,463 امتیاز)
+1
@amir7788 دیدگاهی که پس از آخرین دیدگاهتان در زیر پرسش گذاشتم نگاه کنید. جملهٔ آخر این دیدگاه‌تان نیز از «زنجیر» صحبت می‌کند که با «پادزنجیر» فرق دارد. در این پرسش و یا پاسخ من صحبتی از زنجیر نشده‌است.
توسط amir7788 (2,708 امتیاز)
@AmirHoseinحق باشماست. منظور همان پاد زنجیر بوده مشکل روی بلندترین هر چیزی می باشه حال می خواهد زنجیر یا پاد زنجیر یا...
ویرایش نکردم تا دوستان متوجه اشتباه نوشتاری من شوند.  و تا دوستان نظرشان را مطرح نمایند

حمایت مالی

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