アルゴリズム論特論（塩田）2021年度

アルゴリズム論特論（塩田）第2回 (1)　てんびんクイズ

記号

この講義では、全ての整数から成る集合を $\ZZ$ 、すべての自然数から成る集合を $\NN$ と表すことにします。 $\NN$ には $0$ は入れないことにします。 N は natural number の N で、Z はドイツ語の ganze Zahl の Z です。
今日は小文字のアルファベット $a$ , $b$ , $c$ , $\cdots$ は全て整数を表すとします。

てんびんクイズ

　まず、次のクイズをやってみましょう。

クイズ　十分大きな天秤と、

$a$ グラムと

$b$ グラムの分銅がたくさんあるとき、測ることのできる最小の重さはいくらか？

$a=3$ , $b=5$ のときは？

答え

答え左の皿に 3 グラムの分銅を 2 個、右の皿に 5 グラムの分銅を 1 個乗せると、その差として 1 グラムを測れる。 $3 \times 2 - 5 \times 1 = 1$
$a=5$ , $b=7$ のときは？

答え

答え左の皿に 5 グラムの分銅を 3 個、右の皿に 7 グラムの分銅を 2 個乗せると、その差として 1 グラムを測れる。 $5 \times 3 - 7 \times 2 = 1$
$a=17$ , $b=23$ のときは？

答え

答え左の皿に 17 グラムの分銅を 4 個、右の皿に 23 グラムの分銅を 3 個乗せると、その差として 1 グラムを測れる。 $17 \times (-4) + 23 \times 3 = 1$
$a=6$ , $b=10$ のときは？

答え

答えこれは 1 問目の 2 倍の重さなので、左の皿に 6 グラムの分銅を 2 個、右の皿に 10 グラムの分銅を 1 個乗せると、その差として 2 グラムを測れる。 $6 \times 2 - 10 \times 1 = 2$

　どうやらこんな予想ができそうです：

予想　てんびんクイズの答えは、

$a$ と

$b$ の最大公約数らしい。