سلام
منم فهمیدم که با اصل لانه لبوتری رفتی ولی وستا ولش کردی .
Printable View
سلام
منم فهمیدم که با اصل لانه لبوتری رفتی ولی وستا ولش کردی .
سلام
ثابت کنید که از بین هر شش نفر ، می توان سه نفر طوری جدا کرد که یا دو به دو با هم آشنا ، و یا دو به دو با هم نا آشنا باشند .
سلام
2n+1 چیز در اختیار داریم . ثابت کنید که راه های انتخاب کردن دسته هایی با تعداد فرد برابر راه های انتخاب کردن دسته هایی با تعداد زوج است .
سلام
درون یک مربع به ضلع واحد ، 51 نقطه داده شده است . ثابت کنید درون آنها سه نقطه وجود دارند که در داخل دایره ای به شعاع 7/1 جا بگیرند .
سلامنقل قول:
من این سؤال و با رنگ آمیزی حل کردم ولی حل دیگری هم براش دیدم .
صفحه رو شطرنجی می کنیم . حر کت هایی به صورت (0،1) و (1،0) رنگ خانه را تغییر می دهند . ولی حرکت (1،1) رنگ خانه را تغییر نمی دهد . اگر دنباله ای از خانه ها به صورت سفید ... سفید وجود داشته باشد باید دنباله ای دیگر به صورت سیاه...سیاه وجود داشته باشد که طول دو دنباله مساوی باشد . (چون تعداد خانه های سیاه و سفید برابر است) در نتیجه تعداد حرکت های (1،1) باید زوج باشد . واضح است که باید تعداد حرکت های (1،0) با حرکت های (0،1) برابر باشد و در نتیجه مجموع تعداد آنها زوج است . ولی ما باید تعداد فردی (63)حرکت انجام دهیم . در نتیجه این کار امکان پذیر نمی باشد . :rolleye:
سلامنقل قول:
جدول را به صورت شطرنجی رنگ می کنیم . در حرکت مورچه ها رنگ خانه ی آن ها عوض نمی شود . به راحتی می توان دید بهترین حالت وقتی رخ می دهد که دو مورچه جای خود را با هم عوض کنند . در نتیجه نه مورچه به خانه هایی باید بروند که در آنها مورچه وجود دارد . :sad:
سلام
من صورت سوال صفجه شطرنج 8*8 نفهمیدم.میشه بیشتر توضیح بدین؟
اگه اولین حرکت رو به با لا باشد واضح است که دیگر از خانه های ردیف پایین نمی توانیم بگذریم و اگر هم به سمت راست باشد دیگر از خانه های سمت چپ ترین ستون نمی توانیم بگذریم.اگه هم قطری باشد که نه از ردیف پایین می توان گذشت ونه از ردیف سمت چپ.
سلام ali_hp
در اون سوال به جای حرکت (1،1) حرکت (1-،1-) رو بزار ببین جور می شه .
سلام
n نفر به ضرب سکه مشغولند . برخی تنها سکه ی تقلبی و بقیه تنها سکه ی واقعی ضرب می کنند . وزن سکه ی تقلبی ، با وزن سکه ی واقعی فرق دارد . یک ترازو با گونه های مختلف وزنه و یک سکه ی واقعی در اختیار داریم . از هر کدام از ضرب کنندگان سکه ، هر قدر سکه که بخواهیم می توانیم بگیریم . چگونه می توان با سه بار وزن کردن همه ی کسانی را که به ساختن سکه ی تقلبی مشغولند ، شناخت؟
سلام بر دوستان
امروز می خوام داستان به وجود آمدن استقرا رو در ریاضیات براتون بگم .
کشف استقرا مربوط به فردی ایتالیایی به نام Franciscus Maurolycus است .
در زمان های گذشته وقتی می گفتند x روز قبل از هالیدی ، مشکل اینجا بود که نمی دونستن که باید خود هالیدی و هم با اون روز ها حساب کنند یا نه .
استقرا از اینجا شروع شد که وقتی می گفتند یک روز قبل از هالیدی نمی توانست که منظورشون خود هالیدی هم باشه . در نتیجا یک روز قبل از هالیدی خود هالیدی و در بر نداشت . درتنیجه دو روز قبل از هالیدی هم نمی توانست که خود هالیدی و در بر داشته باشه چون در اون صورت دو روز قبل از هالیدی با یک روز قبل از هالیدی هم معنی می شد . همین طور سه روز قبل از هالیدی هم نمی توانست هالیدی را در بر داشته باشد و الی آخر .
این طور شد که استقرای ریاضی به وجود آمد .
سلام بر دوستان
من یکم فکر کردم گفتم حالا که اتاق ترکیبیات زدم بیام بگم اصلا ترکیبیات چیه ؟
به همین خاطر این مطلب و براتون گذاشتم .
(منبع: جزوه ی دکتر سید عبداله محمودیان مدرس دانشکده ی علوم ریاضی دانشگاه صنعتی شریف)
آنالیز ترکیبی چیست؟
آنالیز ترکیبی که به آن ریاضیات ترکیبی و یا ترکیبیاتی نیز اطلاق می شود ، رشته ای از ریاضیات است که از دوران قدیم آغاز شده است . بنا به افسانه های نقل شده ، یو (yu) امپراطور چین (2200 سال قبل از میلاد) مربعی وفقی زیر را پشت لاک پشت "آسمانی" ملاحظه کرده بود .
2 9 4
7 5 3
6 1 8
جایگشت های آغازی از 1100 سال قبل از میلاد در چین هستند . بیشتر کارهای اولیه در ترکیبیات با اسرار اعداد پیوند خورده است ولی در طول چندین قرن اخیر ، نویسندگان مختلف از نظر یک سرگرمی ریاضی با این موضوع برخورد می کردند . مسأله ی وزنه های باچت (Bachet) ، مسئله ی دختر مدرسه ای های کرکمن (Kirkman) و مسئله ی 36 افسر اویلر از مثال های معروف هستند . مسائل فوق تفکر برانگیز بوده و گاهی اوقات حل آنها ابتکار آمیز و بسیار زیبا هستند .
بسیاری از مسائلی که در گذشته به صورت سرگرمی مطرح شده اند ، هم اکنون ارزش زیادی از نظر علوم محض و کاربردی یافته اند . چندی بیش نسیت که صفحه های تصویری متناهی به صورت یک مسئله کنجکاوانه ریاضیات ترکیبی مطرح می شد . ولی امروزه آنها اساس مبانی هندسه بوده و پایه ای بر تحلیل طرح های آزمایشی هستند . نیاز حیاتی تکنولوژی جدید عصر ما به مباحث کسسته ، از ریاضیات تفننی یک مبحث جدی و جدیدی به وجود آورده است . ولی مهمتر از همه اینکه عصر جدید برای ریاضیات ترکیبی یک حوزه وسیعی از مسائل جدید مجذوب کننده ایجاد کرده است . این مسائل در جبر مجرد ، توپولوژی ، مبانی ریاضی ، نظریه گرافها ، نظریه بازی ها ، برنامه ریزی خطی و بسیاری از موضوعات دیگر ریاضی به وجود آمده اند . ریاضیات ترکیبی دائما در حال دگرگونی بوده است . در زمان ما این دگرگونی از چندین جهت افزایش یافته است ، به طوری که با بسیاری از شاخه های مختلف ریاضی برخورد پیدا کرده است . در نتیجه دادن یک تعریف رسمی از آن مشکل است . ولی کلا می توان گفت که این علم مطالعه ای است روی آرایشها مختلف بر روی اعضای مجموعه ها . مجموعه ها معمولا متناهی بوده و آرایش ها هم با محدودیت هایی که مربوط به هر مسئله است همراه هستند . دو مسئله در حالت کلی مورد برسی هستند :
آیا یک پیکربندی به خصوص روی یک مجموعه ی متناهی وجود دارد یا خیر؟
در صورت وجود پیکر بندی به چند حالت است؟
دوست من خیلی متشکر کپی کردم ..
خواهش می کنم عزیز .
سلامنقل قول:
رأسی را ماند v به دلخواه انتخاب کنید و فرض کنید که حداقل درجه یعنی 1593 است . سپس دیگر رأس ها را در دومجموعه قرار دهید . A مجموعه ای که با رأس مفروض همسایه اند و B رأس هایی که با رأس مفروض همسایه نیستند .
راسی را از همسایه های رأس مفروض در نظر گرفته و حداکثر همسایه های آن را در مجموعه ی B قرار دهید و ...
امید وارم بتونید بقیشو خودتون حل کنید .
سلامنقل قول:
برای هر نفر یک رأس در نظر می گیریم .آشنا ها را با رنگ قرمز و نا آشنا ها را با رنگ سبز به هم وصل می کنیم . در این جمع رأسی به دلخواه را در نظر می گیریم . این فرد یا سه آشنا و یا سه نا آشنا در این جمع دارد . فرض می کنیم که سه آشنا دارد (قرمز). در بین این سه رأس اگر دو نفر همدیگر را بشناسند(با قرمز به هم وصل باشند) با نفر اول تشکیل یک مثلث (قرمز) می دهند و مسئله حل می شود و اگر هیچ کدام دیگری را نشناسد ، این سه نفر با هم تشکیل مثلثی (سبز) را میدهند و باز هم مسئله حل می شود . :laughing:
سلامنقل قول:
هر انتخاب مجموعه ای فرد از این اشیا موجب انتخاب نکردن مجموعه ای زوج می شود . :tongue:
سلامنقل قول:
هر ضلع مربع رو به پنج قسمت تقسیم می کنیم . در نتیجه مربع به 25 مربع کوچکتر تقسیم می شود . اگر در هر مربع کوچک دو نقطه باشد در مجموع می شود 50 نقطه در نتیجه در مربعی وجود دارد که در آن حداقل سه نقطه وجود دارد . دایره ای به شعاع 7/1 می تواند این مربع های کوچک را در خودش جادهد . در نتیجه مسئله حل می شود . ;)
سلامنقل قول:
خوب اینجوری بهتره ولی جواب سوال هنوز غلطه!
سلام.نقل قول:
من منظور اين سوال را متوجه نشدم. "دسته هايي با تعداد فرد" يعني دسته هايي كه تعداد اعضاي هر دسته فرد است يا اينكه تعداد دسته ها فرد است؟
سلام بر دوستان
من خیلی خوشحال شدم که چند نفری هستن که نظر می دن و وقتی من مطلبی رو ناقص می نویسم بهم می گن . چون برای من مهمه که بتونم مطالبو انتقال بدم چون می خوان تو المپیاد شرکت کنم و مصحح های باشگاه خیلی سختگیرن . پس هرچی بیشتر شما بهم ایرادامو بگید من بیشتر پیشرفت می کنم .
خیلی ممنون .
سلامنقل قول:
من خودمم به شک اوفتادم . بزار دوباره فکر کنم جواب دقیق و برات می ذارم .
سلامنقل قول:
منظور تعداد اعضای هر دسته است . مثلا اگر مجموعه کل ما M باشد . زیر مجموعه ی A که تعداد اعضای آن را با نماد |A| نشان می دهند ،اگر فرد باشد ، متمم A را اگر مجموعه B بگیریم ، آنگاه |B| زوج خواهد بود .
سلام
ثابت کنید در یک جمع 18 نفره یا چهار نفر هستند که همگی همدیگر را می شناسند یا چهاد نفر هستند که هیچکدام دیگری را نمی شناسد .
سلام
روی یک صفحه ، m نقطه داده شده است . در ضمن همه ی آن ها روی یک خط راست نیستند . ثابت کنید دست کم می توان به تعداد (m-1)(m-2) (1/2) مثلث پیدا کرد .
سلام
هشت رخ را در خانه های صفحه شطرنج قرار دادیم به طوری که هیچ دوتایی همدیگر را تهدید نمی کنند . ثابت کنید تعداد رخ های خانه های سیاه زوج است .
سلامنقل قول:
هر فرد در بین دیگران یا دست کم 9 نفر آشنا و یا نا آشنا دارد . بدون اینکه به کلی بودن راه حل لطمه ای بخورد می توان فرض کرد ، فرد مشخص A ،در این جمع دست کم 9 نفر آشنا دارد . یکی از این 9 نفر ، و مثلا B ، را در نظر می گیریم . اگر بین 8 نفر دیگر 6 نفر پیدا شوند که هیچ کدام با B آشنا نباشند آنگاه مسئله منجر به مسئله ای می شود که در آن می گوییم بین هر 6 نفر 3 آشنای دوطرفه یا سه نا آشنای دوطرفه وجود دارد می شود . فرض می کنیم B ، در بین 8 نفر دیگر ، سه آشنا و پنج نا آشنا داشته باشد ( زیرا اگر B با چهار نفر آشنا باشد ، این چهار نفر یا دوبهدو با هم نا آشنا هستند که ، در این صورت ، یک گروه چهار نفری مورد نظر تشکیل می شود ، و یا دست کم دو نفر آن ها یکدیگر را می شناسند که ، دز این صورت ، A و B و این دونفر ، گروه مورد نظر را تشکیل می دهند.)
اکنون تعداد آشناها را در این 9 نفر محاسبه می کنیم : روی هم 9 نفرند، هر نفر درت با سه نفر آشناست ، چون هر آشنا دوبار به حساب می آید ، بنا بر این تعداد زوج آشنا ها برابر 2/(3*9) = 5/14 می شود که معنا ندارد . این تناقض ، حل مسئله را تمام می کند .
سلام
اعداد فرد را به صورت زیر نوشته ایم .
1 3 5 7 9
11 13 15 17 19
21 23 25 27 29
31 33 35 37 39
41 43 45 47 49
از این عدد ها 5 عدد طوری انتخاب می کنیم که هیچ دوتایی در یک سطر یا ستون نباشند . ثابت کنید که حاصل جمع 5 عدد همیشه ثابت است .
سلام
K رنگ در اختیار داریم . با چند روش می توان ضلع های یک n ضلعی منتظم را رنگ کرد به نحوی که ضلع های مجاور رنگ های مختلف داشته باشند ؟ (چند ضلعی را نمی توان چرخاند)
سلام
صفحه کاغذ شطرنجی بی پایانی را با 9 رنگ مختلف رنگ کرده ایم . هر خانه یک رنگ دارد و در ضمن از همه ی رنگ ها استفاده شده است . دو رنگ را مجاور می نامیم هرگاه دوخانه که با یک ضلع مشترک پیدا شود که با این دو رنگ ، رنگ شده باشند . حداقل تعداد زوج رنگ های مجاور چند تاست؟
سلام
روی یک صفحه ، m نقطه داده شده است . در ضمن همه ی آنها ، روی یک خط راست نیستند . ثابت کنید دست کم به تعداد 2/1 * (m-1) * (m-2) مثلت می توان رسم کرد که راس های آن روی این نقطه ها باشند .
سلام
در مربع 5*5 ، 16 خانه را رنگ کرده ایم . ثابت کنید ، می توان در آن ، یک مربع 2*2 پیدا کرد که دست کم سه خانه ی آن ، رنگ شده باشد .
سلام
یال های یک گراف کامل را که 2*n+1 راس دارد ، با سه رنگ مختلف رنگ کرده ایم. ثابت کنید ، می توان یکی از رنگ ها و n+1 راس را طوری انتخاب کرد که ، از هر یک از این راس ها به هر راس دیگر از آن ها ، بتوان ار طریق یال هایی حرکت کرد که دارای رنگ انتخابی ما باشند .
سلام
راس های یک گراف محدود با دورنگ مختلف رنگ شده اند . در هر ثانیه ، هر نقطه تغییر رنگ می دهد و به رنگی در می آید که در همسایگی آن بیشتر است . ثابت کنید ، برای هر نقطه لحظه ای فرا می رسد که ، بعد از آن ، یا تغییر رنگ نمی دهد و یا در هر ثانیه ، تغییر رنگ می دهد .
سلامنقل قول:
بدترین حالت زمانی است که m-1 نقطه روی یک خط باشند . برای تشکیل مثلث باید یک نقطه که روی خط نیست و دوتا از نقطه های روی خط را انتخاب کرد که انتخاب 2 از m-1 برابر همان چیزی است که خواسته بودیم .
سلامنقل قول:
خانه ی شطرنج ، وقتی و تنها وقتی سفید است که مجموع شماره های ستون و سطر آن فرد باشد . چون مجموع شماره های سطر ها و ستون ها برای 8 رخ مفروض ، برابر است با 72=(8+...+2+1)2 که عددی زوج است ، بننابر این باید تعداد خانه های با شماره های فرد که در این مجموعه وجود دارند زوج باشد . یعنی تعداد خانه های سیاهی که شامل رخ هستند ، عددی است زوج .:blink:
سلام
این بار یک مقاله آموزشی گذاشتم . این مقاله در مورد نظریه بازی ها است . امید وارم که خوشتون بیاد .
بازی های منصفانه
بازی ها به دو دسته تقسیم می شوند . بازی های پارتیزانی و بازی های منصفانه . بازی های پارتیزانی مانند شطرنج ، گو ، چکرز یا تخته نرد هستند . اما بازی منصفانه به بازی ای می گوییم که مستقل از اینکه نوبت با چه کسی است ، امکانات یکسانی برای دو طرف وجود داشته باشد . اساس بازی های منصفانه بازی نیم است که این بازی به وسیله ی چند کپه ی لوبیا بازی می شود و هر کس در نوبت خود تعدادی (هر تعداد دلخواه) لوبیا از یکی از کپه ها بر می دارد(حد اقل یک لوبیا) . در این بازی و همه ی بازی های منصفانه بازنده کسی است که نتواند حرکتی را انجام دهد . اگر شما بلد باشید که در این بازی چگونه بازی کنید تا نبازید می توانید در همه ی بازی های منصفانه برنده شوید و فقط کافی است که رابطه ای بین بازی ها و کپه های لوبیا بیابید .
حال به چگونه بازی کردن در بازی نیم می پردازیم .
فرض کنید تنها یک کپه وجود داشته باشد . شما کل کپه را بر می دارید و برنده می شوید . پس یک کپه لوبیا وضعیت برد است . حال فرض کنید دو کپه لوبیا در اختیار داشته باشید . اگر تعداد لوبیا در کوپه ها برابر نباشد ، شما کوپه ی بیشتر را هم اندازه با کوپه ی کوچکتر می کنید و از آن پس از اصل مشابه سازی استفاده می کنید . یعنی مثلا اگر حریف شما n لوبیا از یک کپه بردارد شما همان تعداد لوبیا را از کوپه ی دیگر بر می دارید . به سادگی می شود دید که شما برنده می شوید . پس دو کپه لوبیای نامساوی وضعیت برد و دو کپه ی مساوی وضعیت باخت را دارند .
حال اگر تعداد کپه ها بیشتر از دو بود باید چه کار کنیم . عددی که بیانگر تعداد لوبیاهای هر کپه است را در مبنای دو می نویسیم . فرض کنید که ما 4 کپه با اندازه های 27 ، 23 ، 22 و 15 داریم . بست آنها در مبنای 2 به ترتیب برابر 11011 ، 10111 ، 10110 ، 01111 می شود . ( رقم اول از سمت راست برابر یک ، رقم دوم برابر 2 ، رقم سوم 4 و ...) این اعداد را زیر هم می نویسیم . مشاهده می شود که سه تا رقم 1 در جایگاه 16 ، 2 تا در 8 ، 3 تا در 4 ، 4 تا در 2 و 3 تا در 1 وجود دارند . کاری که می باید بکنیم این است که تعداد همه ی این دسته ها را زوج کنیم (حرکت مطلوب می تواند برداشتن 21 لوبیا از کپه ی 23 تایی باشد). حریف ما مجبور است زوجیت را از بین ببرد و ما دوباره کپه ها را اصلاح می کنیم و اگر این کار را ادامه دهیم می بینیم که به برد ما می انجامد . پس وضعیت های برد در نیم دقیقا آنهایی هستند که هر توانی از 2 ، به تعداد دفعات زوج ظاهر می شود .
جمع نیم : جمع در مبنای دو بدون رقم انتقالی ( این یک عمل منطقی است که اغلب در کامپوتر های خیلی کوچک و ماشین حساب ها وجود دارد و آن را احتمالا XOR یعنی یای انحصاری می نامند .)
طبق تعریف داریم : وضعیت های باخت در نیم دقیقا آنهایی هستند که کپه های نیم در آنها اندازه هایی دارند که مجموع نیمشان صفر می شود .
می بینیم که می توان با روش بالا در بازی نیم برنده شد . برای برنده شدن در سایر بازی های منصفانه باید در هر وضعیت کپه نیم معادل را بدست آورید .
اگر مایل بودید که بازی های بیشتری رو یاد گرفته و طریقه ی بدست آوردن مقدار نیم در آن ها را بدانید می توانید اعلام کنید تا بیشتر به مبحث نظریه ی بازی ها بپردازم .
سلام
دوستان اگر نظری دارید ، اگر پیشنهاد یا انتقادی دارید ، اگر مایلید در موضوع معیینی سوال مطرح بشه ، اگر ... لطفا بهم اطلاع بدید . ممنون می شم .
سلامنقل قول:
مسئله را بر اساس زوج یا فرد بودن K حل کنید . اولین ضلع کی می خواهیم رنگ کنیم به K روش رنگ می شود . ضلع مجاور آن با K-1 رنگ و ضلع مجاور ضلع دوم نیز با K-1 رنگ و ...:sad:
سلامنقل قول:
فرض می کنیم این طور نباشد . ستون سمت راست و سطر پایین را در نظر می گیریم . بدیهی است که باید دست کم 8 خانه ی آن ها رنگ شده باشد ( و البته نه هر 9 خانه) و ، در نتیجه ، باید خانه هایی از جدول که پس از حذف 9 خانه ی گفته شده در ستون سمت راست و سطر پایین قرار می گیرند ، بدون رنگ باشند . در نتیجه در مربع 3*3 گوشه ی چپ و بالای جدول ، باید 8 خانه ی رنگی داشته باشیم ، و این ، به معنای آن است که در آن جا مربع 2*2 با سه خانه یا چهار خانه ی رنگی وجود دارد.
سلام
دوستان ، به علت نزدیک شدن امتحان المپیادم تا مدتی نمی تونم به طور منظم سوال بزارم ولی هر وقت تونستم این کار و می کنم . شما به بزرگواری خودتون ببخشید .