معمولا نمیام اینجا ولی این جالب بود:
جواب 4 وزنه هست.
چند نوع ایده غلط هست که سریع به ذهن میرسه اگر این ایده ها به ذهنتون رسید مشکلی نیست یه خورده عجله کردید ولی ذهنتون روشهای خوبی رو امتحان می کنه :
1و2و4و8و16وو32 که میشه 6.
یا از یک روش پله ای استفاده می کنیم: برای تا 40 کیلو یک وزنه 20 کیلو + وزنه هایی فاقد 20 که تا 20 رو بگیره: برای 20: 10 + وزنه های فاقد 10 که تا 10 رو بگیره، برای10 : 5 + فاقد 5 برای تا 5.
حالا با 1و2و3و4 ، 5رو با چندتاش میشه ساخت؟ 3تا: مثلا با 1و2و3 (که میشه ثابت کرد با2تا وزنه نمیشه.) یا بعه عبارتی 3+ تا 2 فاقد 3. که میشه 1و 2
میشه 6تا.
این روش ها هیچ کدوم یک الگوریتم درست نیست چون هر دو در مثال 4 مشکل دارند و جواب 3 عدد 1و2و1 میدهند که جواب درست: 1و3 یعنی دو وزنه هست.
جالا چرا این روشها غلطه؟ چون به دو سمت بودن ترازو دقت نداره.
فرض کنیم وزنه های :
x1,x2,x3,...xn استفاده بشند، سمت راست ترازو رو مثبت وسمت چپ رو منفی میدونیم یعنی آرد سمت چپ هست: با این اعداد باید:
40-,39-,...,2-,1-, + 0 + 2,1,...40,39
که در اینجا میشه: 81 عدد
حالا در هر وزن کشی هر وزنه میتونه سمت چپ، راست یا خارج از ترازو باشه یعنی سه حالت داره:1+و 0 و 1- .
پس نیاز ما به حداقل( در مبنای 3) ( log(81
یعنی 4 وزنه.
حالا میسازیم ولی با وزنه های یکسان کار نمی کنیم ( چون در حالت وجود وزنه یکسان lمثلا x3=x4=1 دیگه 81 عدد ساخته نمیشه چون حالتهای x3-x4 , x4-x3 یا x3*0+x4, x4*0+x3 یکسان میشند وما نمی تونیم به 81 عدد برسیم.) از طرفی چون با 4 وزنه حداکثر ( در حالتی که هیچ دو نوع وزنه گذاری نتیجه یکسان نده ) به 81 می رسیم و 81 هم نیازه پس هیچ دو نوع وزنه گذاری نباید نتیجه یکسان بده:
x1+x2+x3+x4 (biggest number)=40
x1+x2+x3=39(second number)=39
پس:x4=1.
x1+x2+x4 or x1+x2+x3-x4=38 or 37
چون فرق این دوعدد x3-2x4هست و x4=1و x3>=2 پس حالت x1+x2+x3-x4=38 & x1+x2+x4=37 درسته.
پس به سادگی داریم: x3=3.
حالا حالتهای بعدی:
بخش قبل :x1+x2+x4=37 پس x1+x2=36 و پس x1+x2-x4=35 و پس x1+x2+x4-x3=34 و پس x1+x2-x3=33 و پسx1+x2-x3-x4=32.
حالا بزرگترین حالت موجود x1+x3+x4 هست پس: x1+x3+x4=31
پس x1=27 پس x2= 9.
x1=27,x2=9,x3=3,x4=1.
نکته مهم دیگه اینه که اگر تعداد بیشتر از 40 باشه لزوما تعداد هم از 4 بیشتره و اگر کمتر باشه لزوما جواب از 4 بیشتر نیست.
+ وزنه ها همیشه توان 3 هستند که با استقرا یا .... میشه ثابت کرد.
