アルゴリズム論特論(塩田)第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$ の最大公約数らしい。