|
問題1343
3842 g と 1377 g の重りがたくさんある。天秤にこれらを適当に載せて量れる最小の重さはいくらか?またそのとき、重りをどちらに何個載せたらよいか?
解答
under consideration...
・わたしの
まず、同じ重りが両方にあれば相殺されるから、、、それぞれの側には異なる重りだけが載っているはず。
次に、aM-bN=k
とするとき、(a,b,k)=1 であるはず。なぜなら、公約数があるならそれで割った重さは最小のkより小さくなってしまうから。
M,N の最大公約数をGとすると、aM-bN=G(aM'-bN')=k なので、存在する最小のkは、あるなら、k=G,aM'-bN'=1を満たせばよい、
(3842 ,1377)=(3842-2*1377=1088,1377)=(1088,1377-1088=289)
=(1088-3*289=221,289)=(221,289-221=68)=(221-3*68=17,68)=(17,68-4*17)
=(17,0)
3842/17=226,1377/17=81
a*226-b*81=1
b=(a*226-1)/81=2a+(64a-1)/81
64a-1=81b'
a=(81b'+1)/64=b'+(17b'+1)/64
17b'+1=64a'
b'=(64a'-1)/17=3a'+(13a'-1)/17
13a'-1=17b"
a'=(17b"+1)/13=b"+(4b"+1)/13
から、b"=3,a'=3+1=4,b'=3*4+3=15,a=15+4=19,b=2*19+15=53
つまり、19*226-53*81=4294-4293=1 で成り立つ!
結局、最小で量れる重さは、17 g
そのとき、3842 g の重りが 19 個、1377 g の重りが、53 個。^^
結構面倒くさいな。。。^^;
|