Math Battle [ 0002: 不思議な９桁の整数 ]

[ 0002: 不思議な９桁の整数 ]

[ 湯会老人の出題 ]

1 から 9 までの数字を一つずつ使って、
次の条件を満たす 9 桁の整数を作ってください。

上位 n 桁を取り出した数は、n で割り切れる。(n は 1 から 9 まで)

こういう数は 1 個しかありません。見つかるかな？

[ 千手春弥さんの回答 ]

上位桁から順に n₁, n₂, n₃, n₄, n₅, n₆, n₇, n₈, n₉ としましょう。

まず、n₅ は 5 で確定。
n₂, n₄, n₆, n₈ は偶数、すなわち {2, 4, 6, 8} の中の数になる。
* 4 個の数で 4 個の偶数を使い切るため、n₁, n_{3,
n₇, n₉ は残った {1, 3, 7, 9} の中から。}
100 は 4 で割りきれるため、上位 4 桁での n₁, n₂ はどの数でもよい。 n₃ が {1, 3, 7, 9} ならば、n₄ は {2, 6}。
上位 3 桁が 3 で割り切れ、上位 6 桁が 6 で割り切れるためには、 n₁ + n₂ + n₃ も n₄ + n₅ + n₆ も 3 で割り切れる必要がある。 n₅ は既に 5 で確定しているので、n₄ を仮に 6 にすれば、 ₆ は 4 しかない。
上位 7 桁が 7 の倍数になるには:
(n₁ + n₅n₆n₇) - n₂n₃n₄ が 7 で割り切れる。

こうやって絞り込んでゆきますと、
実質的に 24 とおりあたりまで絞り込み (screening) ができるはずです。
あれこれ試した結果は：

381654729

[ 湯会老人のコメント ]

私はこういう場合 Perl スクリプトを書いて、即実行します。次のようなものですね。本当は (1,2,3,4,5,6,7,8,9) の順列 (362880 とおり) を利用したほうが効率がいいのですが。気が向いたら書き直します。

#!/usr/local/bin/perl

for ($n=123456789; $n<=987654321; $n++) {
　$s = sprintf("09d", $n);
　%d = split(//, $s);
　%c = (); # チェックマーク用。
　for ($i=0; $i<9; $i++) {
　　goto NG if ($d[$i] == '0'); # 0を含む数字はNG。
　　goto NG if ($c[$i] == '1'); # 重複した桁を持つ数字はNG。
　　$c[$i] = '1';　# 一度あらわれた桁の数にチェックマークをつける。
　}
　for ($i=0; $i<9; $i++) {
　# 上位($i+1)桁をとった数が($i+1)で割り切れなければNG。
　　goto NG unless (int($n/10^(8-$i)) % ($i+1) == ($i+1));
　}
　print ("Magic number: $n\n"); # 生き残った数を書き出す。

　next;
NG: ;
}

[ 改訂版 ] ⇒ 0170 (順列機能を使用)

[ 浅見多絵さんのコメント ]

なるほど。結構簡単に書けますね。
私も今度機会があったらやってみようかしら。しかし、プログラムにやらせるのはズルいかも。 (笑)

[ 0021: 次の記事 ]

[ 0020: ３個の奇数の和が偶数？ ]

[ 0019: 男女比はどうなるか？ ]

[ 0018: ２本の線で領域分断 ]

[ 0017: 超簡単なMIT入試問題 ]