トランプ５２枚を十分にシャッフルした後、４枚ずつ１３組に分ける。
各組から１枚だけ、あるトランプを抜き出して１３枚のトランプで、１から１３までの数字(マー
クは無視)を揃えられるのか？

　もし、不可能であれば、その組合わせの実例を示してほしい。


　DD++ さんからのコメントです。（令和６年２月２２日付け）

　各組から 1 枚ずつ取り出して全ての数字を揃えたあと、さらに、各組残りの 3 枚から 1 枚

ずつ取り出して再び全ての数字を揃え、さらに、各組残りの 2 枚から 1 枚ずつ取り出して三

度全ての数字を揃え、最後に残った 1 枚ずつがまた全ての数字の組になる……。

……まで、できそうな気がします。ただ、証明は難しそうですね。


　Dengan kesaktian Indukmu さんからのコメントです。（令和６年２月２２日付け）

　よく似た？問題です。

　トランプ 52 枚を十分にシャッフルした後に、テーブル上に 4 行 13 列に並べて初期配置と
します。

　同じ数のカードは 1 対 1 で互いに位置を交換できます。こうした交換は好きなだけ行えま
す。

　ゴールは、全ての列にスペードハートダイヤクローバーを揃えることです。

　任意の初期配置について、必ずゴールすることができるのでしょうか。もし不可能であれ
ばその組合わせの実例をあげてください。

※同じ数のカードとは、たとえば、jack どうしも含みます。

※私はこの問題についてまだよく理解していません。必ずゴールできる気がいたしますが、
　証明といいますか、適切なアルゴリズムが不明です。


　ＧＡＩ さんからのコメントです。（令和６年２月２２日付け）

　通常のトランプで、DD++ さんが言われる現象が起こせるものか直接わかるはずが無かっ
たので、規模を縮小し、{1,2,3,4}の数字が各3枚ずつある計12枚のカードを、3枚ずつで4組を
構成して、異なる組合わせが具体的にどの様になるのかを調べてみました。

　私のプログラムの仕方なので、凄く時間がかかってしまい、12時間ほどの時間を要して、
次の93通りを作れました。

　全部チェック出来たわけではありませんが、ランダムに、10通りほどの別れ方で、1〜4の
数字を3回取り出せるか実験したら、全て可能となりました。

　従って、1〜13の数字が各4個ずつある52枚での通常のトランプで、各組を4枚ずつの13組
を作ったとしても、各組から一枚ずつ取り出すと1〜13のセットを抜き出すことが4回起こせる
ことは十分確からしく起こせると思われました。

　ただ、すべての組合わせが並べられるかと言えば、私のプログラム力ではどうにもなりま
せん。(全部で何通りか計算で求められるものなのでしょうか？)

　また、論理的に証明と言われても手も足も出ません。

　DD++ さんからのコメントです。（令和６年２月２２日付け）

　私が述べた内容が正しいことの証明方針が、手元では立ちました。ただ、これを言葉で伝
わるように記述するのが非常に難しい……。


　らすかるさんからのコメントです。（令和６年２月２３日付け）

　GAIさんへ

　3枚ずつの場合は、数字の種類の数1,2,3,…に対して、

　1, 2, 10, 93, 1417, 32152, 1016489, 42737945, 2307295021,…通り

となり、この数列は、「A254243」にあります。（4番目の93がGAIさんが算出された値です。）

　4枚ずつの場合は、数字の種類の数1,2,3,…に対して、

　1, 3, 23, 465, 19834, 1532489, 193746632,…通り

となり、この数列は、「A268668」にあります。（いずれも数列サイトでは「0種類」からです。）

　よって、「A268668」により、元の問題の場合では、1276433147589499725385063通りであ
ることがわかります。

　このサイトに数式が書かれていませんので、簡単な計算で算出する方法は見つかってい
ないものと思いますが、50種類の数がとんでもない大きさであることから、プログラムでうま
く算出する方法があるのでしょうね。


　DD++ さんからのコメントです。（令和６年２月２３日付け）

　私の考えを記述すると何をどう書いても非常に長い文になってしまい、文字を導入した一
般的な証明ではおそらく非常にイメージしにくいであろうものになってしまいます。

　そのため、例示により考え方だけを書くにとどめます。ここにいるみなさんなら、ご自身で
一般的なものに書き直すのも容易だと思いますので。

　GAI さんの一覧から適当に

43;[[1, 1, 3], [1, 3, 4], [2, 2, 4], [2, 3, 4]]

をお借りして、実際にやってみます。

　これを、「各組の中で順番を並び替えて、任意の i に対し各組の i 番目が全て異なる数で
あるようにする」の手順を以下に記述します。この「　」の操作を、以後整列と表現することに
します。

　まず、2 ヶ所穴あきになっている状態の解法を記載します。

・・・・・ ここから ・・・・・

【問題】(step 1)　[[1, 1, 3], [1, 3, 4], [2, 2, 4], [2, 3, 4]] を整列せよ。

　まず、 最大数である 4 が入っている組を 1 つ選びます。今回は、2 番目の組を選択し、
その組に含まれる 4 には目印に # を付けておきます。

→　[[1, 1, 3], [1, 3, 4#], [2, 2, 4], [2, 3, 4]]

　選択した組以外の 4 と選択した組の 4 以外の数字を 1 対 1 で任意に入れ替えて別の問
題を作ります。入れ替えが起きたものは目印に ? を付けておきます。
（どれとどれを入れ替えたかわかるように、? の個数で区別します）

→　[[1, 1, 3], [4?, 4??, 4#], [2, 2, 1?], [2, 3, 3??]]

　ここから、# 付きの数を含む組を削除し、? の目印を消したものを、問題名に X を付加し
た新しい問題として定義します。以下、一旦新しい問題を解く過程に入ります。

【問題X】　[[1, 1, 3], [2, 2, 1], [2, 3, 3]] を整列せよ。

（ここの解法は穴あき。今回は偶然見つけた解を用いて続きを記述します）

　[[1, 1, 3], [2, 2, 1], [3, 3, 2]] と整列できました。解の一例が得られたので、問題名の末尾
の X を取り除いた問題の step 2 に進みます。

【問題】(step 2)　[[1, 1, 3], [1, 3, 4], [2, 2, 4], [2, 3, 4]] を整列せよ。

　step 1 で、　[[1, 1, 3], [4?, 4??, 4#], [2, 2, 1?], [2, 3, 3??]]　という別の問題を作った状態に
なっていました。

　これに対し、条件付き整列を実行します。すなわち、「ある i について、i 番目には ? 付き
の数が存在しない」が成立しているような整列を行います。

　まず、# 付きの数を含む組以外を普通に整列します。これは、問題名に X を付加した新
しい問題の解を丸ごと再現することで可能です。

→　[[1, 1, 3], [4?, 4??, 4#], [2, 2, 1?], [3, 3??, 2]]

　このとき、# 付きの数を含む組さえ見なければ、「ある i について、i 番目には ? つきの数
が存在しない」が必ず成立しています。

　なぜなら、入れ替えを行なったペアの数は、各組の数字の個数よりも必ず小さいからです。
今回は i = 1 がそれに該当しています。

　その後、# 付きの数を含む組を、i = 1 番目に # 付きの数が来るように順番を入れ替えます。

→　[[1, 1, 3], [4#, 4?, 4??], [2, 2, 1?], [3, 3??, 2]]

　これで、i = 1 番目に ? つきの数がない整列ができました。この状態で入れ替えを戻すと、
元の問題の「とりあえず i = 1 番目には全て異なる数がある」状態になりました。

→　[[1, 1, 3], [4#, 1, 3], [2, 2, 4], [3, 4, 2]]

　ここから、全ての組の i = 1 番目の数を削除したものを、問題名に Y を付加した新しい問
題と定義します。以下、一旦新しい問題を解く過程に入ります。

【問題Y】　[[1, 3], [1, 3], [2, 4], [4, 2]] を整列せよ。

（ここの解法は穴あき。今回は偶然見つけた解を用いて続きを記述します）

　[[1, 3], [3, 1], [2, 4], [4, 2]] と整列できました。解の一例が得られたので、問題名の末尾の
Y を取り除いた問題の step 3 に進みます。

【問題】(step 3)　[[1, 1, 3], [1, 3, 4], [2, 2, 4], [2, 3, 4]] を整列せよ。

　step 2 で、　[[1, 1, 3], [4#, 1, 3], [2, 2, 4], [3, 4, 2]]　と「とりあえず i = 1 番目には全て異な
る数がある」状態になっていました。

　そして、i = 1 番目以外の部分は、問題名に Y を付加した新しい問題の解を利用して整列
できます。

→　[[1, 1, 3], [4#, 3, 1], [2, 2, 4], [3, 4, 2]]

　最後に # の目印を消せば、解の一例が得られます。

→　[[1, 1, 3], [4, 3, 1], [2, 2, 4], [3, 4, 2]]

・・・・・ ここまで ・・・・・

　さて、もちろんこれでは解全体は完成していません。途中の【問題X】と【問題Y】の具体的な
解き方が空白のままですからね。

　しかし、【問題X】は実は最大の数がもとより 1 小さくなった整列問題なので、【問題XX】と
【問題XY】部分が穴あきの同様の解法を用いることができます。

　【問題Y】も同じ数の個数がもとより 1 小さくなった整列問題なので、【問題YX】と【問題YY】
部分が穴あきの同様の解法を用いることができます。

　さらに【問題XX】は【問題XXX】と【問題XXY】部分が穴あきの同様の解法を用いることが
できて……と、この解法は再帰的に用いることが可能です。

　これをどんどん繰り返していくと、そのうち穴あき部分が自明に解ける問題に行き当たりま
す。すなわち、

・問題名に X が 3 個含まれる問題は「1 だけでできた 1 組からなる問題」なので、自明に整
　列できている
・問題名に Y が 2 個含まれる問題は「各数字 1 枚ずつを各組 1 枚ずつにわけている問題」
　なので、自明に整列できている

の 2 種は、穴あき部分は自明に埋まります。よって、最初の【問題】は

【問題】step 1
　【問題X】step 1
　　【問題XX】step 1
　　　【問題XXX】（自明）
　　【問題XX】step 2
　　　【問題XXY】step 1
　　　　【問題XXYX】（自明）
　　　【問題XXY】step 2
　　　　【問題XXYY】（自明）
　　　【問題XXY】step 3
　　【問題XX】step 3
　【問題X】step 2
　　【問題XY】step 1
　　　【問題XYX】step 1
　　　　【問題XYXX】（自明）
　　　【問題XYX】step 2
　　　　【問題XYXY】（自明）
　　　【問題XYX】step 3
　　【問題XY】step 2
　　　【問題XYY】（自明）
　　【問題XY】step 3
　【問題X】step 3
【問題】step 2
　【問題Y】step 1
　　【問題YX】step 1
　　　【問題YXX】step 1
　　　　【問題YXXX】（自明）
　　　【問題YXX】step 2
　　　　【問題YXXY】（自明）
　　　【問題YXX】step 3
　　【問題YX】step 2
　　　【問題YXY】（自明）
　　【問題YX】step 3
　【問題Y】step 2
　　【問題YY】（自明）
　【問題Y】step 3
【問題】step 3

という自明な問題 10 個と非自明な問題 9 個からなる 37 step を踏むことで穴あきのない
完全な解答になります。

13 までの数を 4 個ずつの場合は、自明な問題 455個と非自明な問題 454個の 1817step
必要になるようです。

　トランプ実物を 15 組くらい用意して手作業でやる場合、X が 12 個並ぶまで待たなくても
10 個くらい並んでる問題は気合いでどうにかして短縮できそうです。

　それでも数百 step は必要になるでしょうから根気がとんでもなく必要になるでしょうが。


　Dengan kesaktian Indukmu さんからのコメントです。（令和６年２月２３日付け）

　冒頭の私が提出した問題についてです。以下では便宜のためこの問題を《デンガン》と呼
称します。

　デンガンにおいて初期配置が与えられカードについての所与の交換ルールに従い交換を
繰り返しゴール配置に辿り着けたものとします。

　ゴール配置においては、13ある各列には必ずスペードが１枚づつあります。このスペード
のカードたちは当然ながら１から10,J,Q,Kまでを１枚づつ含みます。

　このスペードのカードの配置位置にマークをつけておいて、52枚のカードの配置を再び初
期配置に戻します。

　さきほどマークをつけておいた13枚分のカードの配置位置(すなわちゴールにおいてはス
ペードカードのみが置かれた位置)について考えますと、初期配置ではスーツがユニークに
はなっておらずバラバラではあります。しかしながらその13枚分のカードの位置にあるカード
たちは１から10,J,Q,Kまでを１枚づつ含みます。

　所与のカードの交換ルールを鑑みればこれは当然のことです。これら13枚を《ストレート》
と呼ぶこととします。

　以上はスペードのみについて考えましたがゴール配置におけるハート、ダイヤ、クローバ
ーの3つのスーツについても同時に同様なことが言えます。

　すなわち、スペードの他にハート、ダイヤ、クローバーのストレートも得られたわけです。

　さて、うえで判明した4つあるストレートは、GAIさんの問題の解になっていることになります。

すなわち、各列から同じストレートのメンバーのカードを拾い上げていけばよいのです。

　初期配置によらずにデンガンの問題に常に解が存在すれば、GAIさんの問題にも常に解
が存在することとなります。

　一日考えましたが、デンガンの問題については列ごとにグリーディーに4スーツをそろえて
いくことを行い、これを繰り返せば、たいがいはうまくいきそう、という感想が得られるのみで
した。証明にはいたりません。


　ａｔ さんからのコメントです。（令和６年２月２４日付け）

　トランプ５２枚を十分にシャッフルした後、４枚ずつ１３組に分ける。
各組から１枚だけ、あるトランプを抜き出して１３枚のトランプで、１から１３までの数字(マー
クは無視)を揃えられるのか？

　必ず１から１３までの数字を揃えることが可能です。これは、グラフ理論の「ホールの定理」
からわかります。

　４枚ずつ１３組に分けたものを、　S_1、S_2、S_3、・・・、S_13　としたとき、

任意の A (A⊂{1,2, ... ,13}) に対して、常に、　|∪[j∈A] S_j| ≧ |A|　が成り立っています。

　よって、{1,2, ... ,13} から {S_1,S_2,S_3, ... ,S_13} への完全マッチングが存在します。


　ＧＡＩ さんからのコメントです。（令和６年２月２５日付け）

　私が、当初 {1,1,1,2,2,2,3,3,3,4,4,4} の１２枚のカードをシャッフルし、３枚ずつの４組に配布
するとき、その異なる配布の組合せが、９３パターンになることを見つけるのに約１２時間も
かけていたことが、次のような考察で同じ結果がほんの数秒で求まることができました。

　異なる４個の素数 (2,3,5,7) を全て掛けた値の３乗の値 (2*3*5*7)^3=9261000 でのすべて
の約数の中で、３個の素数で構成されている約数(bigomega(約数)==3のタイプ)だけを集め
(全部で20個ある。)、この集合で重複を許し４個を取り出した時(全部で、₂₀H₃=1540通り)の
中から、その取り出す４個の積がピタリ 9261000 と一致できるものが何個あるのか調査する。

　このチェックに合格できる数が、求める値と一致できるという。

gp > S=select(x->bigomega(x)==3,divisors((2*3*5*7)^3));･････�@
gp > S
%21 = [8, 12, 18, 20, 27, 28, 30, 42, 45, 50, 63, 70, 75, 98, 105, 125, 147, 175, 245, 343]
gp > #S
%22 = 20
gp > {M=[];}forvec(X=[[1,#S],[1,#S],[1,#S],[1,#S]],\
M=concat(M,[vecextract(S,X)]),1);･････････････････････�A
gp > #select(i->vecprod(i)==(2*3*5*7)^3,M)･･････････････････�B
%24 = 93

　上の実質�@、�A、�Bを組合わせれば済む。


　ａｔ さんからのコメントです。（令和６年２月２８日付け）

　私が、当初 {1,1,1,2,2,2,3,3,3,4,4,4} の１２枚のカードをシャッフルし、３枚ずつの４組に配布
するとき、その異なる配布の組合せが、９３パターンになることを見つけるのに

　20個の x の単項式

　x^111、x^1011、x^1101、x^1110、
　x^21、x^12、x^201、x^102、x^210、x^120、x^2001、x^1002、
　x^2010、x^1020、x^2100、x^1200、
　x^3、x^30、x^300、x^3000

の中から、重複を許して4個を、それらの積が x^3333 となるように選び出すような場合の数
を数え上げてもよいですね。

　この計算を Risa/Asir で実行した結果が以下です。

[0] F=(1+x^10111+x^20222+x^30333)*(1+x^11011+x^22022+x^33033)*(1+x^11101+x^22202+x^33303)
　*(1+x^11110+x^22220+x^33330)*(1+x^10021)*(1+x^10012)*(1+x^10201)*(1+x^10102)*(1+x^10210)
　*(1+x^10120)*(1+x^12001)*(1+x^11002)*(1+x^12010)*(1+x^11020)*(1+x^12100)*(1+x^11200)
　*(1+x^10003)*(1+x^10030)*(1+x^10300)*(1+x^13000)$coef(F,43333,x);
[1] 93

　かなり強引な多項式の展開ですが、一瞬で結果を表示してくれました。


　ＧＡＩ さんからのコメントです。（令和６年２月２９日付け）

　例のやり方で通常のトランプの数字だけに着目した　{1,1,1,1,2,2,2,2,･･･････,13,13,13,13}
の集合で、4枚ずつ13組に分配した時の異なる数字の組の個数を求めることに応用しよう
と試みていたんですが、原理的には13個の異なる素数の積

　(2*3*5*11*13*17*19*23*29*31*37*41)^4

が持つbigomega==4のすべての約数を取り出し、その集合での重複を許して、13個取り出す
ものの積が上記の素数の積を満たす場合の総数を調べればいいことになる。

　但し、すべての約数を並べようとすると大変なので、逆に、bigomega==4になるものを作る
ことをすれば、

gp > P=primes(13);
%136 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
gp > M1=apply(i->i^4,P)
gp > #M1=13 (pi^4型)
gp > M2={M2=[];}for(i=1,13,for(j=1,13,if(i!=j,M2=concat(M2,[P[i]^3*P[j]]))));M2
gp > #M2
%86 = 156(pi^3*pj型);13*12=156)
gp > M3={M3=[];}for(i=1,13,for(j=1,13,if(i!=j,M3=concat(M3,[P[i]^2*P[j]^2]))));M3=Set(M3)
gp > #M3
%91 = 78 (pi^2*pj^2型;binomial(13,2)=78)
gp > M4={M4=[];}forsubset([13,4],i,M4=concat(M4,[vecprod(vecextract(P,i))]));M4
gp > #M4
%139 = 715 (pi*pj*pk*pl型;binomial(13,4)=715)
gp > M5={M5=[];}for(i=1,13,for(j=1,13,for(k=1,13,if(i!=j && j>k && k!=i,\
M5=concat(M5,[P[i]^2*P[j]*P[k]]))))) ;M5=Set(M5)
gp > #M5
%141 = 858 (pi^2*pj*pk型;13*binomial(12,2)=13*66=858)

の5タイプに分かれ、これを合体して、

M＝M1∪M2∪M3∪M4∪M5
#M=1820

従って、この1820個もある集合から重複を許して13個取り出すわけですから、

₁₈₂₀H₁₃=₁₈₃₂C₁₃=4,0291,9125,1047,1060,9784,1375,0687,2800
　（4澗291溝9125穰1047じょ1060垓9784京1375億687万2千8百）

という物凄い場合があり、この中で条件を満たせるものが「A268668」では

　1,2764,3314,7589,4997,2538,5063

というわけですから、約2憶5千万の調査で1個見つかるかどうかぐらいにしかヒットしない。
これではいくら時間をかけても総数を掴むことは不可能に思えた。

　探す位置を絞って、やっと次の3つは発見できました。

1;[16, 81, 625, 2401, 14641, 28561, 83521, 130321, 279841, 707281, 923521, 1874161, 2825761]
2;[16, 81, 625, 2401, 14641, 28561, 83521, 130321, 279841, 707281, 923521, 2076773, 2550077]
3;[16, 81, 625, 2401, 14641, 28561, 83521, 130321, 279841, 707281, 923521, 2301289, 2301289]

　at さんの方法はまだ理解していませんが、もしこれに挑戦したらどうなるんのでしょうか？


　Dengan kesaktian Indukmu さんからのコメントです。（令和６年２月２９日付け）

　「ホールの定理」には、解の存在定理のような印象を受けました。このままですと、数え上
げは難しいような？



　　以下、工事中！