فرض کنیم $2n$ نقطه در فضا داریم و در مجموع $n^2+1$ پارهخط بین آنها رسم شده است. نشان دهید حداقل یک مجموعه از سه نقطه وجود دارد که دو به دو به وسیلهی پارهخطهایی به هم وصل شدهاند.
فرض کنیم $2n$ نقطه در فضا داریم و در مجموع $n^2+1$ پارهخط بین آنها رسم شده است. نشان دهید حداقل یک مجموعه از سه نقطه وجود دارد که دو به دو به وسیلهی پارهخطهایی به هم وصل شدهاند.
# ریاضیات # نظریه گراف # ریاضیات گسسته
عکس نقیض قصیه را اثبات میکنیم. یعنی ثابت میکنیم گرافی که $2n$ رأس داشته باشد و بدون مثلث باشد، حداکثر $n^2$ یال دارد.
برای $n=1$ قضیه به وضوح برقرار است.
فرض کنیم برای گرافی با $2n$ رأس نیز برقرار باشد، قضیه را برای گراف با $2n+2$ رأس اثبات میکنیم.
فرض کنیم $G$ گرافی با $2n+2$ رأس و بدون مثلث باشد. دو رأس $A$ و $B$ از $G$ را که به وسیلهی یک یال به هم متصل شدهاند انتخاب میکنیم. حال $A$ و $B$ و تمام یالهای متصل به آنها را ندید بگیریم.
گراف باقیمانده $G'$ دارای $2n$ رأس و بدون مثلث است. با توجه به فرض استقرا $G'$ حداکثر $n^2$ یال دارد.
$G$ چند یال میتواند داشته باشد؟
هیچ رأسی مانند $C$ وجود ندارد که رئوس $A$ و $B$ هر دو به آن متصل باشند زیرا اگر چنین باشد، $G$ مل یک مثلث است. بنابراین اگر $A$ به $x$ رأس از $G'$ متصل باشد، آنگاه $B$ به حداکثر $2n-x$ رأس از $G'$ متصل است. پس (یالی که $A$ را به $B$ وصل میکند را در شمارش از یاد نبرید) $G$ حداکثر یا یال دارد.
حالت تساوی مسأله نیز برقرار است و در حقیقت میتوان گراف $n^2$ رأسی بدون مثلث را به این روش ساخت:
در واقع $2n$ رأس را به دو مجموعهی $n$ تایی $P$ و $Q$ افراز میکنیم و تمام رئوس $P$ را به تمام رئوس $Q$ متصل میکنیم. گراف حاصل هیچ مثلثی ندارد.
اول مهرماه و 22 بهمن سالی که با سهشنبه آغاز میشود
#ریاضیات #نظریه اعداد #ریاضیات گسسته #معما
1399/02/14-17:45 1 پاسخ
باقیماندهی تقسیم $3^{36} - 2^{36}$ بر $35$
#جبر #جبر و احتمال #ریاضیات گسسته
1399/02/16-22:33 1 پاسخ
قرار گرفتن $7$ مسافر در یک اتاق سه تخته و دو اتاق دو تخته
#نظریه احتمالات #جبر و احتمال #ریاضیات گسسته
1399/02/18-22:56 1 پاسخ