Terence Tao 教授がお子さんの宿題に難しいパズルが出ていて驚いたということが紹介されています。
パズルの内容は以下のとおりです:
Three farmers were selling chickens at the local market. One farmer had 10 chickens to sell, another had 16 chickens to sell, and the last had 26 chickens to sell. In order not to compete with each other, they agreed to all sell their chickens at the same price. But by lunchtime, they decided that sales were not going so well, and they all decided to lower their prices to the same lower price point. By the end of the day, they had sold all their chickens. It turned out that they all collected the same amount of money, $35, from the day's chicken sales. What was the price of the chickens before lunchtime and after lunchtime?
一見それほど難しいように感じませんが、実際に解いてみると結局多少のプログラミングを利用することになりました。以下はその筋道を紹介するもので、最後に解答を書いています。
ひとまずパズルの内容を式で表現してみます。まず3人の農夫(売り手)がそれぞれお昼前までに売ったニワトリの数をそれぞれ(登場順に) a、b、c とします。そして3人全員が合意したお昼前までの価格を p ドル、また3人全員でお昼過ぎてから安売りしたときの価格を q ドルとします。
1日の売上は3人とも同じ35ドルなので、以下のような式が成り立ちます:
ただし上の等式に表れていない重要なポイントがあり、それは(ニワトリは1羽ずつ売られているので)a、b、c は必ず非負整数値を取るということです。この時点でこのパズルは制約問題として integer programming の知識があれば解けるということが分かります。ただここではそのような知識を仮定しません。
上の等式に
という r を考えると見通しがよくなります:
さらに a、b、c を右辺にまとめると以下のようになります:
特に式(5)と(14)、(15)から
であることも分かります。
まずは「p、q がともにドルの単位で表せる、つまりともに整数になる」という前提で考えてみます。
そうすると式(6)および(16)から、q = 1 でなければなりません。なので式(3)および(4)が成り立つ整数の組み合わせ (c, p, q) は {(1, 10, 1), (3, 4, 1), (9, 2, 1)} の3通りしかありません。 ところが、これらはいずれも式(1)に式(5)の範囲での整数解がありません。つまり「p、q ともに整数」という前提だと解が見つからないことが分かります。
では次に「p、q ともにセントの単位で表せる」という前提で考えてみるとどうでしょうか。これはつまり、「p = p'/100 および q = q'/100 となる整数 p' および q' で解になるものがある」ことを意味します。
ここで式(12)、(13)、(14)、(16)を変形して、q' についての式にします:
式(17)、(18)および(19)の右辺の分子に注目します。等式の左辺はいずれも整数であり、共通の分母を持つので、右辺の分子に表れる3つの数の最大公約数が大きくなることが予想されます。そこで、Scheme で簡単なプログラムを用意して、q' が取り得る範囲の整数を並べ上げて最大公約数を計算してみます。
gosh> (define (nums qq) (list (- 3500 (* 10 qq)) (- 3500 (* 16 qq)) (- 3500 (* 26 qq))))
nums
gosh> (map (lambda (qq) (apply gcd (nums qq))) (iota 134 1))
(2 4 2 4 10 4 14 4 2 20 2 4 2 28 10 4 2 4 2 20 14 4 2 4 50 4 2 28 2 20 2 4 2 4 70 4 2 4 2 20 2 28 2 4 10 4 2 4 14 100 2 4 2 4 10 28 2 4 2 20 2 4 14 4 10 4 2 4 2 140 2 4 2 4 50 4 14 4 2 20 2 4 2 28 10 4 2 4 2 20 14 4 2 4 10 4 2 28 2 100 2 4 2 4 70 4 2 4 2 20 2 28 2 4 10 4 2 4 14 20 2 4 2 4 250 28 2 4 2 20 2 4 14 4)
250が一番大きく、期待できそうです。250になるのはq' = 125のときです:
gosh> (filter (lambda (qq) (= 250 (apply gcd (nums qq)))) (iota 134 1))
(125)
ではこの3つの分子の比はどうなるかというと:
gosh> (map (lambda (n) (/ n 250)) (nums 125))
(9 6 1)
きれいに整数の比が出てきました。これがa、b、c になりそうです。
これで解がp' = 375 および q' = 125 であることが分かりました。つまり、答えはお昼前の価格が3ドル75セント、お昼過ぎてからの価格が1ドル25セントになります。