اتاق ریاضیات(طرح سؤالات)

**lebesgue** · 10-12-2010, 21:20

نوشته شده توسط قله بلند [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

ای کاش زودتر این راه حل رو می دادید. خیلی گشتم.
آیا این لم دارای قضیه ای است؟ از چه آدرسی یا کتابی می شه به اون رسید؟

اثباتش خیلی سادست، با برهان خلف.
فرض کنید i و j ای وجود داشته باشه که این قضیه برقرار نباشه، یعنی:

$\120dpi \\gcd(x_i,y_j)=a\neq 1\: \: \rightarrow\: \: a\mid x_i \:\: and\:\: a\mid y_j\\ \rightarrow a\mid x_1...x_n \:\: and\:\: a\mid y_1...y_m\: \: \rightarrow a\mid gcd(x_1...x_n,y_1...y_m)$

که نتیجه بدست اومده با فرض در تناقضه.

نوشته شده توسط قله بلند [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

استنباط شما از جمله
A set of [logk] pairs of numbers derived from the ni
سقف logk مرحله است؟ چون شما فرمودید که 4 مرحله داریم. من این رو مثلاً 4 جفت از اعداد مشتق شده در نظر می گرفتم.

فرقی نمی کنه، چون بحث (اگر اشتباه نکنم) مربوط به بهینه سازی الگوریتم ها بود، من از مرحله استفاده کردم.
یعنی محاسبه هر gcd رو یک مرحله فرض کردم.
میشه اینطور گفت که شما برای تشخیص اینکه آیا یک مجموعه 16 عضوی، Pairwise coprime هست یا نه (اعضای اون دو به دو نسبت به هم اول هستند یا نه)، کافیه 4 تا gcd خاص رو بدونید (و البته نه اینکه هر 4 تا gcd این خاصیت را داشته باشند).

در مورد پست بالایی، بله درست گفتید.

**قله بلند** · 11-12-2010, 11:13

سلام
شما فرمودید که در بخش بهینه سازی الگوریتم ها این لم آمده است.
من می گم چرا این کار رو نمی کنن:

Gcd(abc,d)=1

وقتی که می دانیم که این 4 عدد صحیح، دو به دو نسبت به هم اولند. با یک گام همه چیز حله.

**قله بلند** · 12-12-2010, 15:42

سلام
ببخشید که دوباره سوال می کنم چون دچار مشکل شدم. خواهش می کنم پاسخ بدید چون واقعاً گیر کردم و اعصابم دیگه داره خط خطی می شه.
1-

کد:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

2-

کد:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

3-

کد:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

5-حالا فرض کنید می خواهم عدد پنجم را وارد کنم تا همگی دو به دو اول باشند. حالا نمی دانم چه کار کنم؟
در این فرمول ها، همیشه از اطلاعات گام قبل استفاده می شود و قبل از ورود عدد پنجم ما می دانیم که 4 عدد قبلی دو به دو اول هستند ولی چه طوری عدد پنجم را با این خصوصیات وارد کنم؟

کد:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

در اینجا عدد 6 نسبت به 11 اول است ولی نمی شود حکم داده که نسبت به 3 عدد دیگر نیز اول باشد. پس چه طوری گام سوم رو وارد کنم؟

**lebesgue** · 12-12-2010, 18:24

نوشته شده توسط قله بلند [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

وقتی که می دانیم که این 4 عدد صحیح، دو به دو نسبت به هم اولند. با یک گام همه چیز حله.

خب اگر بدونید دو به دو نسبت به هم اولند که دیگه چیزی برای حل نمی مونه!
مسئله اینجاست که به شما یک مجموعه مثلا 10 عضوی میدن و شما قراره با صرف کمترین وقت و محاسبات، تعیین کنید که آیا این مجموعه Pairwise coprime هست یا نه.
من روندی که شما میخواین طی کنید رو متوجه نمی شم، اگر هنوز ابهامی هست، صورت مسئله ای که باهاش درگیر هستید رو بطور دقیق اینجا بنویسید.

نوشته شده توسط قله بلند [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

در این فرمول ها، همیشه از اطلاعات گام قبل استفاده می شود و قبل از ورود عدد پنجم ما می دانیم که 4 عدد قبلی دو به دو اول هستند ولی چه طوری عدد پنجم را با این خصوصیات وارد کنم؟

همه مسئله مربوط به همون لم* که نوشتم میشه، پیشنهاد می کنم یه مقدار روش فکر کنید.
شما کافیه بدست بیارید gcd(e , abcd) =1 تا بتونید نتیجه بگیرید e نسبت به هر 4 عدد a , b , c , d اول هست.

*لم معمولاً به قضیه ای گفته می شه که ازش برای اثبات قضایای مهمتر استفاده میشه، یعنی خودش یک قضیه هست.

**lebesgue** · 12-12-2010, 19:31

نوشته شده توسط AryanShining [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

سلام فكر مي كنم تاپيك رو درست اومدم
دنبال اثبات آخرين خاصيت جز صحيح هستم موقعي كه دبيرستان بودم بلدش بودم ولي الان يادم رفته
اين زير خاصيت رو مي نويسم

کد:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

این چیزیه که الان به ذهنم میرسه، نمیدونم چقدر بر راه حل مورد نظر شما منطبق هست.
کافیه برای x در بازه (1 , 0] این مطلب رو نشون بدید، چون در حالت کلی قسمت های صحیح از جزء صحیح بیرون میان و از طرفین خط می خورن.

$\120dpi \\\left \lfloor nx \right \rfloor=k\: \: \rightarrow\: \: k\leq nx< k+1\: \: \rightarrow \: \: \frac{k}{n}\leq x< \frac{k+1}{n}\\\\ 0\leq i\leq n-k-1:\: \: x+\frac{i}{n}<\frac{k+1}{n}+\frac{i}{n}\leq \frac{n}{n}=1\: \: \rightarrow \left \lfloor x+\frac{i}{n} \right \rfloor=0\\\\ n-k\leq i\leq n-1:\: \: x+\frac{i}{n}\geq \frac{k}{n}+\frac{i}{n}\geq \frac{n}{n}=1\: \: \rightarrow \left \lfloor x+\frac{i}{n} \right \rfloor=1\\\\ \sum_{i=0}^{n-1}\left \lfloor x+\frac{i}{n} \right \rfloor=\sum_{i=n-k}^{n-1}1=k$

(n عدد صحیح مثبت است)

**قله بلند** · 12-12-2010, 20:20

سلام
جناب 1233445566 عزیز
می تونم خواهش کنم یک مثال برای

کد:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

و یک مثال برای

کد:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

بزنید. من هر چی تلاش می کنم نمی شه. می خوام ببینم شما چطوری این تقسیم بر دو رو انجام می دید. طبق همون لم.

**lebesgue** · 12-12-2010, 20:53

نوشته شده توسط قله بلند [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

سلام
جناب 1233445566 عزیز
می تونم خواهش کنم یک مثال برای

کد:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

و یک مثال برای

کد:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

بزنید. من هر چی تلاش می کنم نمی شه. می خوام ببینم شما چطوری این تقسیم بر دو رو انجام می دید. طبق همون لم.

برای اولی: میتونید خودتون n6 , n7 , n8 رو به مجموعه اضافه کنید (البته باید هر سه، نسبت به 5 عدد دیگه اول باشند).
بلدید در سه مرحله نشون بدید که این مجموعه 8 عضوی Pairwise coprime هست. خب از اینجا نتیجه می گیرید که هر زیر مجموعه اونهم Pairwise coprime هست!

میتونید برای سادگی هرسه n6 , n7 , n8 رو برابر 1 انتخاب کنید.
دومی هم بطور مشابه!

**AryanShining** · 12-12-2010, 21:27

نوشته شده توسط 1233445566 [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

این چیزیه که الان به ذهنم میرسه، نمیدونم چقدر بر راه حل مورد نظر شما منطبق هست.
کافیه برای x در بازه (1 , 0] این مطلب رو نشون بدید، چون در حالت کلی قسمت های صحیح از جزء صحیح بیرون میان و از طرفین خط می خورن.

$\120dpi \\\left \lfloor nx \right \rfloor=k\: \: \rightarrow\: \: k\leq nx< k+1\: \: \rightarrow \: \: \frac{k}{n}\leq x< \frac{k+1}{n}\\\\ 0\leq i\leq n-k-1:\: \: x+\frac{i}{n}<\frac{k+1}{n}+\frac{i}{n}\leq \frac{n}{n}=1\: \: \rightarrow \left \lfloor x+\frac{i}{n} \right \rfloor=0\\\\ n-k\leq i\leq n-1:\: \: x+\frac{i}{n}\geq \frac{k}{n}+\frac{i}{n}\geq \frac{n}{n}=1\: \: \rightarrow \left \lfloor x+\frac{i}{n} \right \rfloor=1\\\\ \sum_{i=0}^{n-1}\left \lfloor x+\frac{i}{n} \right \rfloor=\sum_{i=n-k}^{n-1}1=k$

(n عدد صحیح مثبت است)

دستت درد نکنه
این چیزی که شما نوشتی تو ذهنم نبود دنباله یه چیز دیگم احتمالا تا چند روز دیگه تو کتاب ها پیداش می کنم اگه پیدا شد حتما اینجا می ذارمش
ضمنا در مورد مطلبی که نوشتی بگم خیلی جالب و به کارم خورد و حتما این رو به استاد نشون می دم واقعا ممنون

**قله بلند** · 12-12-2010, 22:11

سلام
ببینید، من این کار رو انجام می دم:

کد:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

حس می کنم درست نیست.
اینهمه خواهش کردم که راه حلش رو بنویسید.

**lebesgue** · 12-12-2010, 22:39

نوشته شده توسط قله بلند [ برای مشاهده لینک ، با نام کاربری خود وارد شوید یا ثبت نام کنید ]

سلام
ببینید، من این کار رو انجام می دم:

کد:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

حس می کنم درست نیست.
اینهمه خواهش کردم که راه حلش رو بنویسید.

الان اینها چی هست؟
بطور واضح بفرمایید صورت مسئلتون چیه که "این کار رو" براش انجام می دید!

نام تاپيک: اتاق ریاضیات(طرح سؤالات)

اختيارات تاپيک

این کاربر از lebesgue بخاطر این مطلب مفید تشکر کرده است

Thread Information

Users Browsing this Thread

User Tag List

قوانين ايجاد تاپيک در انجمن