2008/04/02
Document Actions
四角い頭を丸くする算数の問題をPythonで解いてみる
今日、電車で見かけた算数の問題。
回文数
"121" や "3333" のように右から読んでも左から読んでも同じ並びになる数値を回文数とよぶことにします。 この回文数について以下の問いに答えなさい。
問い1
5を掛けると回文数となる、3桁の数値のうち最大の数値を答えなさい。
この問題をPythonでプログラムを書いて解いてしまったんだけど、落ち着いて考えれば暗算で解けそう。というか後から考えてみたら暗算で解けた。あああ、もったいないことをした。
ということで以下コード。
- In [1]: def check(n):
...: sn = str(n)
...: for i,s in enumerate(sn):
...: if sn[-(i+1)] != s:
...: return False
...: return True
In [2]: for n in range(999,0,-1):
...: if check(n*5):
...: print n, n*5
...: break
...:
119 595
答えは119らしい。5倍した回文数は595。実はもっと大きな値になると思っていた。
今度は証明っぽく解いてみる。長いこと証明書いてないので書き方の定石は忘れちゃった。
問い1の証明
最大値が999なので、5倍した最大値は4995。ところで5倍すると言うことは下一桁がかならず0か5になるので、最上位桁も0か5にならねばならない。しかし最上位桁が0というのはこの場合あり得ないため、下一桁は5であると言える。また、5倍した値が4桁だと仮定すると積は5000～5999ということになるが、最大を超えるのでこれもありえない。
ここで3桁で最上位桁が5の値について考えると、商は5n5となり、nは0～9どれでも5で割れるので、最大値の9を採用する。
以上により、商=595, 解=595/5=119.
とけた。ポイントが分かれば簡単やね。
書き写し間違ってるかもしれないけど問い2、問い3。また電車の中で考えよう...
問い2
15で割り切れる3桁の回文数のうち、最も大きい数を答えなさい。なお答えに至る過程についても述べなさい。
問い3
15で割り切れる4桁の回文数のうち、商が回文数となる値を答えなさい
# 回文数で検索するとけっこうヒットする
- Category(s)
-
python
- The URL to Trackback this entry is:
- http://www.freia.jp/taka/blog/559/tbping
わーい、「続きを読む」前に正解を出せたぞ。
「5倍した値が4桁だと...」の部分はいらないような気がしますが……。
# あとs/商/積/？
1. 5の倍数では1の位の数字は5または0である。
2. 3桁の回文数はABAの形をとる。ただしAは0でない。
3. 1., 2. から求める回文数は5n5の形をとる。この形をとる最大の整数は595である。
4. 595/5=119、よって答は 119。
おしまい
自分はこんな感じで解きましたが、ロジカルになってるかな。
# 関係ないけどわたくしも幼少のみぎり四角い頭を丸くするところにかつて通っておりました。
Pythonで書くなら……、これじゃだめ？（笑）
print [x for x in range(100, 1000) if x % 5 == 0 and x / 100 == x % 10][-1] / 5
>「5倍した値が4桁だと...」の部分はいらないような気がしますが……。
「5を掛けると回文数となる3桁の数値」なので、
「3桁の回文数」ではなくて「3桁の数字 * 5 = 回文数」なのですよ。（電車で見間違えてなければ）
> # あとs/商/積/？
おおう。修正！
> 「3桁の回文数」ではなくて「3桁の数字 * 5 = 回文数」なのですよ。
あーっ、なるほど！ 失礼しました。
くやしいから修正したワンライナーを……。
max(x for x in range(100, 1000) if str(x * 5) == ''.join(reversed(str(x * 5))))
# 1000 のところの桁を増やしてくとちょっと興味深い（総当たりだから超遅いけど）。
一応暗算でできた。ABBAは 0 でも5 でもなりたたないからABAで、あとはすぐですね。でも問2はそしたら一瞬じゃないの？
解けた。回答は↑のリンクに。
問2：5x5として(5+x+5)mod3=0なxの最大値
問3：5xx5として(5+x+x+5)mod3=0なxは3通り。
15で割って回文数になるのは1通り。
みんなに解かれちゃって、解く楽しみが。。悔しいので短く速くしちゃう。
> max(x for x in range(100, 1000) if str(x * 5) == ''.join(reversed(str(x * 5))))
max(x for x in xrange(999,99,-1)if`x*5`==`x*5`[::-1])
上限を上げると確かに興味深い解が...
おー、コメント付いてますね。
呑み会でしこたま飲んだ後、電車の中で頭の中ぐるぐるしながら暗算で解いた記憶がｗ
名前入れ忘れました。
>上限を上げると確かに興味深い解が...
以下問い1のn桁版の証明。
問い：5を掛けると回文数となる、3桁の数値のうち最大の数値を答えなさい。
回答：
5倍して得られる数の1の位は0, 5 のいずれかであるため題意を満たすのは5.
よって、得られる回文数は以下のいずれかである.
i) 5○○○○...○5 (n+1桁)
ii) 5○○○○...○5 (n桁)
i) の場合、5で割るとn桁にならないため不適. ii) の形について考える。
求める数を X(n) とすると回文数は 5X(n) であり、
5X(n) = 5*10^n + a1*10^(n-1) + a2*10^(n-2) + ... + an-1*10 + 5
(ただし a1, a2, ..., an-1 ∈ {0, 1, ... , 9})
両辺を5で割り、
X(n) = 10^n + 2a1*10^(n-2) + 2a2*10(n-3) + ... + 2an-1 + 1
上記の形から、a1, a2, ..., an-1 の値がいくつであっても X(n) は整数となる。
題意を満たすように a1, a2, ..., an-1 の値を定めると、
a1 = a2 = a3 = ... = an-1 = 9
よって、得られる X(n) は
X(n) = 10^n + 2*9*10^(n-1) + 2*9*10^(n-2) + ... + 2*9 + 1
= 10^n + 1 + 2*9*(10^(n-1) + 10^(n-2) + ... + 1)
= 1000...0 + 1 + 18*(111...1)
= 1000...0 + 1 + 199...8
= 1199...9
以上.
しまった。max()だと高速じゃないや。().next()にしないと。
証明おもしろい。学生時代にこういう問題に遭遇したかったなあ。
> max(x for x in xrange(999,99,-1)if`x*5`==`x*5`[::-1])
おお、スライスのステップ数に負の値を入れるとそうなるんですか。reversed() に入れても元のシーケンスと同じ型でじゃなくてジェネレータで返ってきたから、「おや」とは思ったんですが。
`x` も、こんなシンタックスシュガーが Python にあったのかという感じで、なんだか意外です。
いいこと知りました。
`x` は __repr__ が呼び出されます。str(x)は __str__ が呼び出されます。
str()の代替ではないのでご注意を...
> str()の代替ではないのでご注意を...
あ、補足どもです。