به جون بچم نفهمیدم چی گفتی من رشتم انسانیه الگوریتم نمن دی (چیه)؟

" target="" title="">

" target="" title="">

در واقع میتونستید به روشی راحت تر به جای استفاده از اون ترفند توان 10 بگید1 +[log n]..

بنام خدا

اثبات کمی طولانی اما پیچیده نیست

تعاریف:

^--a^--: تعداد ارقام a

^--ab^--: تعداد ارقام ab

قبل از اثبات به چند نکته توجه شود :

نکته1. واضح است که ارقام خاصیت جابجایی دارند

نکته2. با توجه به نکته 1نظم خاصی را در چینش اعداد رعایت میکنیم وآن اینکه ابتدا اعداد با ارقام بیشتر رامینویسیم 

 

و اما چند لم قبل از شروع :

لم 1(با توجه به نکته 2):اگر^--a^--=n, ^--b^--=m,n≥m آنگاه ^--a+b^--=n یا  ^--a+b^--=n+1

لم 2(با توجه به لم 1): اگر a+b=k آنگاه max ^--ab^--=2*^--k^—

àmax ^--b^—=nàmax ^--ab^—=2*^--k^—کوچکترین عدد باn رقم^--k^—=nà a=

واما شروع بحث :

هر عددی دارای نهایت و بالاترین توانی از 10 می باشد که ما آن را بصورت  10^nنمایش می دهیم. برای اثبات حالت کلی را در نظر میگیریم که درآن تمام اعداد دارای حداکثر توان  10^n لحاظ شوند

به این ترتیب عددی با حداکثر توان 10^n در گام بعدی بصورت n+1,a,b در خواهد آمد که در آن   a+b= n+1

(هر عددی با حداکثر توان 10^n دارای n+1  رقم خواهد بود)

 

می خواهیم بدانیم حداکثر ارقام عدد جدید چه تعداد است؟

با توجه به فرم عدد جدید و لم 2 داریم :

^--n+1,a,b^—=3*^--n+1^—

شرط 1.همچنین داریم اگر(همواره برقرار) 10^(m+1)>n+1≥10^m  آنگاه ^–n+1^—=m 

پس با شرط 1 لازم است دو عدد 10^n  و 3m را از لحاظ تعداد ارقام مقایسه کنیم

از آنجا که 10^n≥10^((10^m)-1)> 10^(10^(m-1))

 با مقایسه 10^(10^(m-1)) و 3m متوجه کم شدن ارقام در هر گام خواهیم شد

مشکل همینجاست.. باید اینو اثبات کرد..

سلام
خب این روندی که گفته شده عدد را کوچک و کوچک تر میکنه
اونقدر که هر عددی را در نهایت به یه عدد 3 رقمی کوچک و تبدیل میکنه
وقتی به 3 رقم رسید الزاما یکی از اعداد زیر خواهد بود
303
312
321
که هر سه عدد بالا در گام بعدی به 312 تبدیل میشن و این چرخه در 3 رقم بسته میشه و جلوتر نمیره

من مثال رو برای فهم بهتر نوشتم وگرنه بدون مثال فکر کنم توضیحش کامل بود یکبار دیگه تلاش می کنیم :
می دانیم که همواره تعداد ارقام یک عدد از خود آن عدد کوچکتر است .(بجز صفر که کاری با آن نداریم)
پس اگر تعداد رقم های عدد abcd... , فرضا efgh... تا باشد و ijkl... تا از آنها زوج و mnop... تا از آنها فرد باشند و طبق الگوریتم بنویسم داریم efgh...ijkl...mnop
حال مقصود ما آن است که بدانیم آیا تعداد رقم های abcd... بیشتر است یا تعداد رقم های  efgh...ijkl...mnop
2 حالت خاص وجود دارد که آنها را بررسی و از سر راه بر می داریم :
حالت اول آن است که عدد اولیه ی ما یک رقمی باشد و حالت دوم آن است که عدد اولیه دو رقمی باشد که در هر دو حالت با یک مرتبه پیشروی در الگوریتم به مقصود خود یعنی عدد 3 رقمی می رسیم اما به محض آنکه عدد ما 4 رقمی شد مطمئنا :
1 : تعداد رقم های عدد ما از خود عدد کوچکتر است
2 : در ماکزیمم حالتی که تعداد ارقام ijkl... و mnop... با تعداد ارقام efgh... برابرند تعداد ارقام حاصل شده 3*تعداد ارقام efgh... خواهد بود
برای آنکه ثانویه ای که بدست می آوریم 3*(تعداد ارقام q) رقمی شود در حالت ماکزیمم می بایست عدد اولیه ی ما q رقم داشته باشد
حال باید اثبات کنیم که به ازای q>2 با استفاده از استدلال استقرایی عددی که تعداد ارقامش q تاست از عددی که تعداد ارقامش 3*(تعداد ارقام q )تاست بیشتر است که با اجازتون هنوز اثباتش نکردم ولی فکر کنم کاری نداشته باشه( خداییش حوصله می خواد ولی اثباتش از راه شهودی واقعا واضحه) به محض اثبات شدن این موضوع به این نکته می رسیم که تعداد ارقام همواره سیر نزولی را طی می کنند تا جایی که به 3 رقم برسند که به مقصود خود در دو تا پست قبلی می رسیم. 

 شما نظری ندارید؟

چه راجع به 1 میلیون دلار و چه مسئله..

 قبول.. اما باز هم خیلی خاص شد.. مشکل اینجاست که تو راه حل مسئله به صورت کلی ضعیف عمل شد و باز هم مجبور شدید واسه قانع کردن خواننده دست به مثال بزنید.. سعی کن کلیش کنی..

می دانیم که همواره تعداد ارقام یک عدد از خود آن عدد کوچکتر است غیر از عدد صفر پس اگر فرضا عدد ما 20 تا رقم داشته باشه و 10 تاش زوج و 10 تاش فرد باشه داریم 201010 درسته که یک عدد 6 رقمی هست و باز می رسیم به 642 که عددی 3 رقمی هست خود 201010 یک abcd... جدید هست پس بطور خلاصه اگر طبق الگوریتم شما پیش بریم بالاخره به عدد می رسیم که تعداد ارقامش یک عدد یک رقمی باشه و به محض رسیدم به چنین عددی ما داریم ( nm(n-m...

خیلی سربع به این نتیجه نرسیدید؟

  این سوال رو جایی دیدم که مورد تایید بود .. خواهم گفت

فرض می کنیم عدد داده شده abcd... باشد اگر تعداد ارقام n باشد داریم و تعداد ارقام زوج m حتما تعداد ارقام فرد n-m خواهد بود حال داریم( nm(n-mحال دوباره می بینیم که تعداد ارقام 3 تا شده
اگر n عددی زوج بود :
 3 حالت ممکن است روی دهد 1 : تعداد ارقام زوج با تعداد ارقام فرد یکسان باشد 2 : تعداد ارقام زوج از تعداد ارقام فرد بزرگتر باشد 3 : تعداد ارقام فرد از تعداد ارقام زوج بیشتر باشد تک تک حالات را بررسی می کنیم ابتدا حالت اول : در این صورت هم m  و هم n-m عددی زوج اند پس عدد نهایی می شود 330 که با یک مرحله ی دیگر پیشروی داریم 312 حالت دوم و سوم حالاتی بودند که تعداد ارقام فرد با زوج متفاوتند در این حالات 2 حالت دیگر پیش می آید یا هر دو تعداد زوج و فرد، زوجند یا هر دو فردند . در حالت اول داریم 330 که دیدیم شد 312 یا هر دو فردند که داریم 312
اگر که n فرد باشد :
در این حالت مطمئنا تعداد ارقام زوج با فرد متفاوت است و یکی زوج است و دیگری فرد چون جمع تعداد ارقام زوج و فرد اگر هر دو زوج و یا هر دو فرد باشند عددی زوج می شود و می دانیم که n فرد است پس یا m زوج است و n-m فرد و یا n-m زوج است و m فرد که در هر دو حالت می شود 312 پس ما با بررسی تمامی حالات پی بردیم که می شود 312 اگر جواب درست بود بی زحمت این 1 میلیون و برام بفرستین

اون وقت این جایزه یک میلیون دلاری رو کجا میدند بریم بگیریم؟