【数セミ】エレガントな解答をもとむ3【2018.10】

**１３２人目の素数さん** · 2018/09/17(月) 01:40:43.02

締切りの過ぎた問題をみんなで議論しましょう。

過去スレ：
1. http://rio2016.5ch.net/test/read.cgi/math/1295154182/
2. http://rio2016.5ch.net/test/read.cgi/math/1476702312/

**１３２人目の素数さん** · 2020/06/11(木) 04:05:02.72

出題1、結果だけならプログラム組めば出せる
無論、そこにエレガントさはカケラもない。

1から2倍と桁入れ替えで到達可能な数をリストアップすると、以下を除く4桁の数(5558個)になった。
これらが1に到達不可能なことを確かめるのは難しくない。

・3の倍数
・全ての桁が奇数
・全ての桁が2か6
・1114, 1141, 1411, 4111, 1118, 1181, 1811, 8111, 2228, 2822, 2282, 8222, 4444, 8888

**１３２人目の素数さん** · 2020/06/11(木) 04:16:45.02

まず、3の倍数であることは(1)(2)で変わらない。

最大n回(2)が可能、で考察すると
0回：全ての桁が奇数
1回：全ての桁が2か6、1114, 1141, 1411, 4111, 1118, 1181, 1811, 1110, 1101, 1011
これは下2桁が4の倍数+2、2で割って千の位が奇数、2で割って十の位が奇数、を考えればよい。

2倍→桁を入れ替え→2で割る、という手順でここから抜けられない数を順次リストアップしていくと
2回：2228, 2822, 2282, 8222, 4444, 2220, 2202, 2022
3回：8888, 4440, 4404, 4044
4回：8880, 8808, 8088
5回：なし

となって、上記に含まれない数は手順を選べば無限回(2)が可能。
蜂の巣原理から、その手順のどこかで桁の組合せが同じ数に戻る。
……までは考察できたが、それが1に到達可能な数という保証ができないな。

**１３２人目の素数さん** · 2020/06/11(木) 04:33:35.28

読み直してみると、途中で3桁に落ちるパターンが考慮から漏れているかな。
3桁でも同じようなことを考えることはできそうだが。

**１３２人目の素数さん** · 2020/06/11(木) 09:39:36.05

・3の倍数
　1002から9999まで　 3000個
・全ての桁が奇数 {1,3,5,7,9}
　5^4 -　208 (3の倍数) = 625 - 208 = 417個
・全ての桁が {2,6}
　2^4 - 4 (2が3個) -1 (6666) = 11個
・{1114} {1118} {2228}, 4444, 8888 = 14個
・{1110} {2220} {4440} {8880} は3の倍数 = 0個

ここまで 3442個 (到達不能)

・全体で
1000から9999まで　9000個

・上記のリストにないものは
9000 - 3442 = 5558個