【パズル】3種の数字でできる3桁の数列を部分数列として、その全て（111～333）を含む最小長さの全体数列を考えて下さい。

Question

やまだまや（真優）

66

64もっと見る

500pt

学習・教育ゲーム

【パズル】3種の数字でできる3桁の数列を部分数列として、その全て（111～333）を含む最小長さの全体数列を考えて下さい。

また同じく4種の数字でできる4桁の数列を部分数列として、その全て（1111～4444）を含む最小長さの全体数列を考えて下さい。
5種以上で同桁の同様の数列でもかまいません。（当方は、3桁、4桁での抜け、重複をチェックできるプログラムは作りました。）
ちなみに数字種N(桁数N)の場合、全体数列の最小長さL＝N^N＋N-1と言うことは判っています。
N=1の場合,数字種'1'として,部分数列'1',全体数列＝'1',L=1
N=2の場合,数字種'1.2'として、部分数列'11.12.21.22',全体数列＝'11221',L=5
となります。ちなみにN=3の時L=29,N=4の時L=259,N=5の時L=629です。
N=3とN=4の例解（基本パターンの１つ）は終了後、発表します。（基本パターン1つに付きその変形はN=3で27ｘ3ｘ2通り、L=4で256ｘ4ｘ2通りはあるようです。
文字の場合、数列を文字列、数字種を文字種と読み替えてください。

＊正解が無数にある問題なので終了後のコメントでの回答も1ヶ月間、評価対象とします(ポイント送付にて）

回答の条件

1人5回まで

登録：2011/06/17 23:52:30
終了：2011/06/24 23:55:12

※ 有料アンケート・ポイント付き質問機能は2023年2月28日に終了しました。

Mook 2011/06/18 12:53:25

数列の使用方法が、数学の用語とは異なった意味で使用されているようですが、
質問中の意味での「全体数列」の一パターンが求めたいということでしょうか？
それともすべてのパターンを羅列したいということでしょうか。
やまだまや（真優） 2011/06/19 12:33:06

Mookさん、回答は『「全体数列」の一パターン』で結構です。全てのパターンを羅列することは、「はてな」では無理だと思いますよ。（時間的にもスペース的にも）

全体が何パターンあるかは計算してません。2数の場合は基本パターン数x数転置ｘ逆順（２）で4種類です。基本パターン数と転置と逆順がラップしてます。
３数以上では数転置ｘ逆順（２）でできるものは１パターンと数えられます。
『数学の用語とは異なった意味で使用されているようですが』
正確な数学用語の用法から外れていると思いますが、ニュアンスで捉えてください。
やまだまや（真優） 2011/06/21 00:38:33

余談ですが、5数（5種の数字（文字）を使ったと言う意味です）での抜け、重複をチェックできるプログラムも先日作成し、動作確認もしました。・・・表が大きいので大変でした、どこが（どの数列が）重複しているかがわかるのは3,4数のときと同じですが、隠れる部分が多いので、一箇所でも重複が発生すると赤く変わるセルをいつも見える位置に設置しました（Excelでさくせいしたものですから、他のプログラム言語ならばモット単純に作成できたと思います。)それで赤のセルが表示されると、表を移動させてどの数列に重複が発生したかをみるわけです。
これは、問題を解くプログラムではありません、あくまでチェック用です。
問題を解くのは、頭と筆記用具です。だから、3数か4数が手ごろだと思います。
Mookさんは説いてくれましたが、5数以上は、筆算では頭が疲れるだけの問題だと思います。
Mook 2011/06/21 12:25:32

質問の意図が手での算出を意図されていたら済みませんが、今回の回答はプログラムで計算しています。
N=5 までは楽勝（N=5 では2分程度）だったのですが、N=6は24時間以上やっても解けませんでした。

EXCEL(VBA)を使用したので、結果的にはセルにかける文字が32768文字（N=6の桁数は46661）までという制限により、最初の初期データを作った時点でおかしくなっていたのですが、その問題が無くとも数十時間はかかりそうな計算量だったと思います。

ここまでくると、やまだまやさんの質問の意図から完全に脱線していますが、Cに移植して再挑戦したいと思っています。
余力があったら、N=3での全パターン列挙も試してみます。
やまだまや（真優） 2011/06/21 12:59:24

Mookさん、有難うございます。　
『質問の意図が手での算出を意図されていたら済みませんが、今回の回答はプログラムで計算しています。』の返信ですが、私は
「パズル」にするなら（頭と紙での手算出では）３、４数が限界だろうという意味で「プログラム使用禁止」という意味ではありません。５数の回答は大変助かりました。５数の数列も３１２９桁の数字の列をExcelに貼り付けて、関数で１桁ずつ区きり、チェックプログラムに貼り付けて、完璧だという事が確認できました。（昨日は頭が回らなくて）
『余力があったら、N=3での全パターン列挙も試してみます。』もありがたい事ですが、あくまで遊びですので。パターンが何通りか有るかだけでも、ゲーム性は有望だと思っているのですが。質問文で書いた。（基本パターン1つに付きその変形はN=3で27ｘ3ｘ2通り、L=4で256ｘ4ｘ2通りはあるようです。）は最低でもこれだけはある事は容易に予想できるという事で正確ではないかもしれません。もしMooｋさんが出してくださる全パタン数（仮にAとして）１６２A種のバライティが期待できますので。－－－－甘い考えですかねぇ？
Mook 2011/06/22 08:07:31

全パターンと言っていたのは、バリエーションも含めての話ですので、その数はバリエーション数（162？）の倍数かもしれませんが、それ以上ではありません。

ですが、ギブアップです。
解はせいぜい数百通り～数千通りくらいかと高をくくっていたのですが、N=3ですら検索範囲の組み合わせパターンがべらぼうなオーダーになることに気が付きました。
とりあえず手あたりしだいに計算して、あたりを付けようと思ってやってみたのですが、
8時間ほどで65000パターンに達した以降も、一向に減衰する様子が見えません。
よっぽどうまい枝刈りの方法が見つかるか、論理的にパターン数を計算できないと、現実的な時間で終わるかどうか判断が付きそうもありません。

ですがいろんなパターンを見てみて気が付いたのですが、最初の（N-1)桁と最後の（N-1)は必ず同じになるのですね。ごく一部の抜粋ですが、こんな感じです。
vv_________________________vv
13222311122121331233323211313
21213331323211311123122233221
23311333222131323212111231223
33132221113332321311212312233

指数関数的に増加するとは爆発的な増加を指しますが、たかだか30桁程度とはいえ 3^29 は十分「ばかでかい」数でした。
やまだまや（真優） 2011/06/23 01:36:23

Mookさん、苦労をおかけします。
『最初の（N-1)桁と最後の（N-1)は必ず同じになるのですね。』は最初の予想でわかっていました。部分数列（要素）がN^NあるのだからN^(N＋１）桁あれば十分で要素が重複する事も容易にわかります、またN^N桁では全要素ができない事もわかります。それで最後の桁に最初のN-1桁が最小だろうとよそうしてました。が果たしてそれでNがいくらになっても全要素が網羅できるかわからなかったので、前の質問で何桁になるか問うたのですが、私の質問の仕方が悪かったので、回答はなく、質問はキャンセルしました。
それで、今回は1,2,3,4桁まで実際にN＾N+N-1で全要素が求まる数列が作れるのを確認したから、質問内容をかえました。

私が質問前に作成し、チェックした数列パターンは以下の通りです。Mookさんから頂いた回答とはパターンが異なることは確認しました。
（左から右へ、次の段の左から右への様に数字をつなげて読んでください）

3数
111 222 333
331 112 223
131 212 323
---
11

4数
1111 2222 3333 4444
1133 2244 3311 4422
1313 2424 3131 4242
1331 2442 3113 4114
---- ---- ---- ----
1432 2143 3214 4321
1234 2341 4123 3241
1243 2314 4132 3343
2444 2142 1212 2433
---- ---- ---- ----
3234 4124 1223 2324
3431 4131 1142 2212
3123 2234 3341 2132
2241 3342 4414 2331
---- ---- ---- ----
3422 4232 1343 4211
1321 2422 3133 3143
4134 4241 4443 4431
2113 1221 1431 1214
---- ---- ---- ----
111

これで1パターンですが、1基本パターンからできるバリエーションも（チェックプログラムで）確認しました。
まず、数字を入れ替えても成り立つやり方を　A
　　　開始位置をずらしすやり方を　B
　　　（おまけの無い部分の）数列を逆から並べるやり方　C（＝２）　とします。
そうすると　基本パターン*（A*B*C)となりそうですが、かなり同じものもできそうです。

A：数字を入れ替えるやり方
3数の時　A3:１＞２＞３＞１（と逆入れ替え）と
　　　　　A2:１＞２＞１（３は触らない）２＜＞３，１＜＞３があります。
4数の時　
　　4数の入れ替え　A4:1＞2＞3＞4＞1、1＞4＞3＞2＞1、1＞3＞2＞4＞１など、
3数の入れ替え　A3:1＞2＞3＞1、(4は触らない）など　
　2数のみの入れ替え　A21:1>2>1,3>4>3,1>4>1,2>3>2,1>3>1,2>4>2
　2数と2数の入れ替え　A22:1>2>1＋3>4>3,1>4>1＋2>3>2,1>3>1＋2>4>2
5数の時
　5数の入れ替え　A5:１＞2＞3＞4＞5＞1（と逆入れ替え）と
１＞3＞5＞2＞4＞1（と逆入れ替え）
　4数の入れ替え　A4:1＞2＞3＞4＞1、1＞4＞3＞2＞1、1＞3＞2＞4＞１など、
3数のみの入れ替え　A3:1＞2＞3＞1、(4、5は触らない）など　
　2数のみの入れ替え、2数＋2数、2数＋3数

B　開始位置をずらしすやり方
例えば1111からはじめるか1122から創めるかN^N個の開始位置がとれる。
　
C 逆順：これは清純とあわせて２種類
Mook 2011/06/24 08:06:36

B はおそらくやまだまやさんと同じことだと思いますが、最初と最後の（N-1)が同じと
いうことは、片側のN-1を取り除いた N^N の文字列は循環しているのではないかというのが
私の推論です。
つまりこの文字はどこから始めてもよく、最後に最初の2文字を付け加えることで循環形
になるのではということです。

そうすると N=3のとき、 A は6通り、Bは27通り（N^N）、Cは2通りですから、一つの
パターンから324通（162はCが抜けていた？）りのバリエーションが発生します。
論理的な検証はできていませんが、一応いくつかの解から上記バリエーションを作成し、
すべてが111～333を網羅した数値列になることはこちらもで確認しました。

これにより、昨日作成した65000の中の重複確認を行ってみましたが、600までやってみて
（生成よりチェックの方が100倍くらい時間がかかっています）約1%の重複が含まれて
いました。
この状況から考えると、基本パターは N=3のときにだいたい数億のオーダーでしょうか。
バリエーションを含めると兆に届くかもしれません。

まだ検証が1%なので誤差が大きいとは思いますが、やまだまやさんの言うところの「清純」パターンが10万程度検証できれば、全体数のもう少し正確な推定ができそうです。

N=3 だからまだ手が動きますが、N=4ともなると計算でしか取り扱えないですね。
数学では「有限」ですが、人間にとっては「無限」とも思えそうな数になりそうです。
やまだまや（真優） 2011/06/24 23:58:19

Mookさん、ありがとうございます。
無謀にも（恐れ知らずに）１～９を使う「数独」のパタン数と比較したくなりました。
数独のパターン数については下記の確認は取れています（作成できる問題数でなく、完成パターン数ですが）
-----------------------------------------------------------------------
数独の数え上げの現状

Ed RussellとFrazer Jarvisにより、5472730538個であることが知られています(対称性を考慮しない場合は、Bertram FelgenhauerとFrazer Jarvisにより、6670903752021072936960個)。
問題数についてはわかりませんでした。
----------------------------------------------------------------------
この問題の9数の場合（111111111~9999999999)の全パターン数のほうが多くなるのではないかと思えるのですが胴でしょう？・・・「それがどうした、何の役に立つ」と言われれば・・・「むむむむむ」としかいえませんが、3数で解にこれだけバラエティがあれば十分楽しめるかも・・・と甘い期待をまだ持っています。（実際は（解くのと確認に頭を痛める）だけのモノかもしれませんが・・・おそらくみんな「111」から始めると思います。
Mook 2011/06/25 12:14:32

余り根拠もありませんがこの問題での9桁の方がおそらく遥かに大きいでしょう。
今回の問題がどのような形でパズルとなるのか、よくわかっていませんが
数独と比較するのが9桁が妥当かがそもそも怪しい気がします。

数独は現実的にパズルの問題とすることが可能な規模ですが、9桁（9種）のパターンを
網羅する数字列は3億8千万桁以上ですから、そもそも現実的な問題になりえないの
ではないかと思います。

ご自身も書かれていますが、この問題を手と頭で解くことを前提とするなら、3 か
4 がせいぜいでしょうか。
虫食い算的な問題になるとしたら 4 は現実味がない気がします。
やまだまや（真優） 2011/06/25 16:44:01

Mookさん、ありがとうございました。数独は「虫食い算」が本命であり、完成形を問題にする事は無いでしょう、一方、こちらは虫食い算は意味が無いと思います。やはり現実的に「負け」です。この問題はパズルとしてはあまり頭のトレーニングにもなりそうも無いですね。

他に回答し忘れた方：１ヶ月いないのコメントは評価します。（但し既出でない事）
Mook 2011/06/25 19:49:21

虫食い算はないですか？

たとえば「111～333が含まれるように下記の□に1～3を入れて完成させよ」
　□112□1213□11□□□2□23231233131□1
のような問題はできないでしょうか（上のは捻っていないのでやまだまやさんだったら
即答だとは思いますが）。
やまだまや（真優） 2011/06/25 21:58:31

実は、私パズルを解くのは『超超超苦手』なんです。他人の作った問題に「ケチ」つける【クレーマー】と呼ばれています。
威信？？？をかけて解きました。”３３３”が無いので3連空白のところ入れるところから初めました、後は空白一つを利用して、まだ現れてない数字を探して入れました。
案外、虫食い算もできるものですね。（迂闊でした）出題時の問題作成は「数独」より、難しい様におもいます。
回答は　｛□は1、２，２，３，３，３，２，１｝
’111221213211333222232312331311’+‘１’だと思います。最後の１が多い様におもいますが。(30桁あります）
やまだまや（真優） 2011/06/25 22:20:37

『そうすると N=3のとき、 A は6通り、Bは27通り（N^N）、Cは2通りですから、一つの
パターンから324通（162はCが抜けていた？）りのバリエーションが発生します。』の部分も確認してみました。Mookさんの記述の通りでした。
一応３、４，５，６，７と使用する（並び換えする）数字の数別に色々試してみましたが、ややこしくなってトータルがいくらになるか分からなくなりましたが、数字の並び替えなのでAはN!だと気がつきました。基本パターン1つの変形はA＊B＊CでBはN^N,Cは２（メイン部分の正・逆順）すがN=１、とN=２の時は例外になりそうです。・・・1番単純な部分に例外が有るなんて！
兎に角、３以上はN!＊N^N＊２＊基本パターン数になりそう。（肝心の基本パターン数をが判らないなんて！理論としてはいい加減の極みかも）
Mook 2011/06/26 09:54:19

正解です。出題ミスまで指摘いただき、ありがとうございました。
□112□1213□11□□□2□2323123313□1
が問題のはずでした。

最初と最後の2文字は同じだから
1112□1213□11□□□2□232312331311

333がないから
1112□1213□113332□232312331311

最後(最初)の"11"を除くと、すべての数字は9個ずつだから、2だけが足りないので
11122121321133322232312331311

といった感じで解けることを想定してました。
パターン数はおそらく数千億程度だと思いますので、列挙することには意味はなさそう
です。
もう少し数学的な規則性を見つけ出し、それを満たす組合せを論理的に算出しないと
数字としては求められないと思います。

数学の問題としても面白い問題だと思いますが、難題そうです。
やまだまや（真優） 2011/08/01 17:53:30

１ヶ月待ちましたが、Mookさん以外に、回答もコメント回答も無かったのは、寂しいですね。回答はほぼ無数にあるだろうに。

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

リクエスト送信済

回答リクエストを送信したユーザーはいません

Mook · Accepted Answer · 2011-06-20T00:25:58+09:00

1パターンでよいということなので、一応回答です。

111～333を網羅した数字列

11121131221231321332223233311

1111～4444を網羅した数字列

1111211131114112211231124113211331134114211431144121213121412221223122412321233123412421243124413131413221323132413321333133413421343134414142214231424143214331434144214431444222232224223322342243224423232423332334234323442424332434244324443333433443434444111

おまけですが、

11111～55555を網羅した数字列

111112111131111411115111221112311124111251113211133111341113511142111431114411145111521115311154111551121211213112141121511222112231122411225112321123311234112351124211243112441124511252112531125411255113121131311314113151132211323113241132511332113331133411335113421134311344113451135211353113541135511412114131141411415114221142311424114251143211433114341143511442114431144411445114521145311454114551151211513115141151511522115231152411525115321153311534115351154211543115441154511552115531155411555121221212312124121251213212133121341213512142121431214412145121521215312154121551221312214122151222212223122241222512232122331223412235122421224312244122451225212253122541225512313123141231512322123231232412325123321233312334123351234212343123441234512352123531235412355124131241412415124221242312424124251243212433124341243512442124431244412445124521245312454124551251312514125151252212523125241252512532125331253412535125421254312544125451255212553125541255513132131331313413135131421314313144131451315213153131541315513214132151322213223132241322513232132331323413235132421324313244132451325213253132541325513314133151332213323133241332513332133331333413335133421334313344133451335213353133541335513414134151342213423134241342513432134331343413435134421344313444134451345213453134541345513514135151352213523135241352513532135331353413535135421354313544135451355213553135541355514142141431414414145141521415314154141551421514222142231422414225142321423314234142351424214243142441424514252142531425414255143151432214323143241432514332143331433414335143421434314344143451435214353143541435514415144221442314424144251443214433144341443514442144431444414445144521445314454144551451514522145231452414525145321453314534145351454214543145441454514552145531455414555151521515315154151551522215223152241522515232152331523415235152421524315244152451525215253152541525515322153231532415325153321533315334153351534215343153441534515352153531535415355154221542315424154251543215433154341543515442154431544415445154521545315454154551552215523155241552515532155331553415535155421554315544155451555215553155541555522222322224222252223322234222352224322244222452225322254222552232322324223252233322334223352234322344223452235322354223552242322424224252243322434224352244322444224452245322454224552252322524225252253322534225352254322544225452255322554225552323323234232352324323244232452325323254232552332423325233332333423335233432334423345233532335423355234242342523433234342343523443234442344523453234542345523524235252353323534235352354323544235452355323554235552424324244242452425324254242552432524333243342433524343243442434524353243542435524425244332443424435244432444424445244532445424455245252453324534245352454324544245452455324554245552525325254252552533325334253352534325344253452535325354253552543325434254352544325444254452545325454254552553325534255352554325544255452555325554255553333343333533344333453335433355334343343533444334453345433455335343353533544335453355433555343443434534354343553443534444344453445434455345353454434545345543455535354353553544435445354543545535544355453555435555444445444554454544555455454555551111

蛇足ですが、N=5の時はL=3129でしょうか。

L＝N^N＋N-1 はそのようになりますし、上記の結果もそうなりました。

【パズル】3種の数字でできる3桁の数列を部分数列として、その全て（111～333）を含む最小長さの全体数列を考えて下さい。

ベストアンサー

Mook13143932011/06/20 00:25:58

コメント（16件)

この質問への反応（ブックマークコメント）