|
問題3675(友人問) 格子上の次の A~E の5点に友人たちがそれぞれ以下のような人数います。 A:(1,7) に3人、B:(2,1) に2人、C:(3,5) に1人、D:(5,3) に2人、E:(7,2) に5人。 これから、全員が集合することになりました。 全員の移動距離の総和を最小にする地点は以下のどこにすればよいでしょうか? 1. (4,3) の地点 2. (5,2) の地点 3. (5,3) の地点 4. (6,3) の地点 5. (6,2) の地点 解答 ・わたしの 地道に... (x,y)とする...
3|x-1|+2|x-2|+|x-3|+2|x-5|+5|x-7|...
x=4で...9+4+1+2+15=31x=5で...12+6+2+10=28 x=6で...15+8+3+2+5=33 3|y-7|+2|y-1|+|y-5|+2|y-3|+5|y-2| y=2で...15+2+3+2=22 y=3で...12+4+2+5=23 けっきょく...(5,2) ♪ もっと論理的に出せないのかなぁ...^^;? ・友人からのもの 各地点からの移動距離の総和を s とする。 たとえば I 図の位置のA,B に m,n人 (m > n)がいるとき、s を最小にする地点は X なら、s=am+bn だが、m > n なので、Aのときが最小になる。このことは、距離 aとb の値に関わらず、人数の多い地点がs を最小にすることを意味している。 II 図のように3つの地点がある場合の s を最小にする地点は、人数が最大の Cではなく、Bです。なぜなら Aの2人が Bに移動すれば 6人になり、5人を上回るからです。ただし、もし Cの方の人数が 7人であれば、6人を上回るので s を最小にする地点は Cです。 では本問。III 図は横方向に見たものです。AとBがCに移動すると6人。EがDに移動すれば7人。したがって s を最小にするのは Dの地点です。(x座標が5) IV 図は縦方向に見たものです。AとCがDに移動すると6人。BがEに移動すると7人。したがって s を最小にするのは Eの地点です。(y座標が2) よって、 s を最小にする集合地点は (5,2) の格子点ということになります。 ♪...なるほど...理解できるけど...すぐに気付けない...これって...実用的な問題ですよね...^^v
|

- >
- Yahoo!サービス
- >
- Yahoo!ブログ
- >
- 練習用


