『今週の問題』第216回　解答

◆広島県　清川　育男 さんからの解答

3ⁿ個　n回以外、規則性が判りません。

 3個    1 回で達成

 6個    3 回で達成

 9個    2 回で達成

12個    3 回で振り出しに戻る

15個    4 回で振り出しに戻る

◆東京都　明 さんからの解答

【問題１】

９回

【問題２】

[求め方１]

１回のシャッフルでカードがどのように動くかを記述します。
【問題１】の例では以下のようになります。

1　2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18   
3  6  9 12 15 18  2  5  8 11 14 17  1  4  7 10 13 16

1→3→9→8→5→15→7→2→6→18→16→10→11→14→4→12→17→13→
（カードの動きは逆回りとなります。）

このシャッフルの仕方によれば、カードの列の真ん中（この例では9と10の間)を中心として対称の位置（逆順の位置）のカードは対称的な動きをすることが判ります。
したがって、上記のように作成されたループの中に、逆順の位置のカードが１対でもあれば、ループに属する他のカードもループの中に逆順のカードを持ち、すべてのカードが同一回のシフトで、逆順のカードの位置に移ることが保証されます。

【問題１】では「1」に対し逆順の「18」のカードがループ内にありますので、他のカードを確認することなく、逆順に並ぶことを言うことができます。
この場合「1」が逆順の「18」に到達する数９回が必要なジャッフルの数です。

ｍ＝9（ｎ＝27）のときループは次の６個になります。

• 1→3→9→27→25→19→
• 2→6→18→26→22→10→
• 4→12→8→24→16→20→
• 5→15→17→23→13→11→
• 7→21→
• 14→

各ループが逆順に並ぶまでの移動回数をj,kとすると、同時に逆順に並ぶためには、
適当なp,qに対し、j+2pj=k+2qk
よって　j(2p+1)=k(2q+1)とならなければいけません。

したがって、ループのカードの数が　2ⁿ×奇数　で表わされるとき２の冪数が同じであれば同時にループが逆順に並ぶことが保証できます。

（ループのカードが１つのものは、中心のカードで不動です。）

以上から、ｍ＝9の場合も逆順に並ぶことを言えます。
この場合３回ですべてのループのカードが逆順の位置に並びます。

[求め方２]

1　2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18   
3  6  9 12 15 18  2  5  8 11 14 17  1  4  7 10 13 16

Ｋ_j-1＝7　でＫ_j＝2となるとなることから
Ｋ_j≡3Ｋ_j-1（mod　19）を考えます。

Ｋ_j-1＝13　でＫ_j＝1ですので、
これもＫ_j≡3Ｋ_j-1（mod　19）が成立します。

一般的にＫ_j≡3Ｋ_j-1（mod　n+1)が成立することが確かめられます。

したがって逆順に並ぶかは、任意のkに対し、適当なpで下記の式が成立するかを確認すればよいことになります。
n+1-k≡3^p・k（mod　n+1)

変形して、（3^p+1)k≡0　（mod　n+1)

よって　3^p≡-1≡n（mod　n+1)　を満足することが必要十分条件です。

n＝18の時、p＝9 で、n＝27の時、p＝3 で上式が成立します。
p が逆順に並ぶためのシャッフルの回数となります。

【問題３】

【問題２】の方法でｍ＝3^q　(q≧1)の自明解はありますが、一般解は個別に確認する以外、うまい方法は解りませんでした。
計算機で逆順になる場合のｍをリストアップしてみましたが規則性が見出せません。

逆順となるｍ
1,2,3,6,8,9,10,11,12,14,16,19,20,22,24,25,26,27,32,34,35,41,42,44,46,・・

少し前、５２枚のカードを２つに分けて交互に混ぜ合わせるシャッフルを８回（この場合、前のカードを先に入れる）繰り返すと全く元へ戻るというＴＶ番組をやっていました。
（カードマジックでは基本的な技だそうです。）

これも合同式で２⁸≡１（ｍｏｄ５１）で説明できることを理解しました。
カード遊びの中に数論の種が潜んでいるのが面白いですね。

◆愛知県　Y.M.Ojisan　さんからの解答

【問題１】　９回

【問題２】

　（−ｍ）^ｓ≡−１　mod （Ｎ＋１）　となる　ｓ

【問題３】

上記　ｓ　が存在するとき。

∵　この置換は規則的であり、横一列の位置を左から　０，１　・・・　Ｎ−１と番号付けるとき、
ｓ回目のシャッフル後に　Ｉ_ｓの位置にあった数字は　ｓ＋１回目には

Ｉ_ｓ＋１＝２ｍ−ｍ*Ｉ_ｓ　mod （Ｎ＋１）

の位置にあります。

この一般項を解くと

Ｉ_ｓ＝Ｋ＋（−ｍ）^ｓ*（Ｉ_０−Ｋ）　mod （Ｎ＋１）、

ここで　Ｋ＝

２ｍ １＋ｍ

です。

逆順に並んでいるには少なくとも　
（−ｍ）^ｓ　≡−１　mod （Ｎ＋１）　でなければなりません。
さらに　Ｉ_０＝０が　Ｎ−１の位置に来れば完全に逆順が成立します

即ち　３ｍ−１＝Ｋ（１−（−ｍ）^ｓ）　mod （３ｍ＋１）　かどうかが問題です。

ｍ　が偶数のときＫの分母の１＋ｍと１＋３ｍは互いに素です。　
従って単純に、

（３ｍ−１）（ｍ＋１）−４ｍ＝−２ｍ−２−４ｍ＝０　mod （３ｍ＋１）

で成立しています。

ｍ＝２ｑ−１（奇数）のとき　Ｋ＝

２ｑ−１ ｑ

、

３ｍ＋１＝２（３ｑ−１）　
３ｍ−１＝２（３ｑ−２）　　
であるので、

３ｑ−２＝

２ｑ−１ ｑ

ｍｏｄ　（３ｑ−１）　であればよく

（３ｑ−２）ｑ−（２ｑ−１）＝−ｑ−２ｑ＋１＝０　ｍｏｄ　（３ｑ−１）　である。

以上から　　（−ｍ）^ｓ≡−１　mod （Ｎ＋１）　となる　ｓが存在すればｓ回目に逆順になります。

なお　−ｍと　Ｎ＋１＝３ｍ＋１は互いに素なので　　
（−ｍ）^ｓ'≡１　mod （Ｎ＋１）　になるｓ'は必ず存在します。
つまりｓ'回目に元に戻ります。

これ以上は一般化できなかったので、ＰＣ解をｍ＝１〜５０に対して示します。
空欄は解がないケースです。

m	N	s	s'
1	3	1	2
2	6	3	6
3	9	2	4
4	12		3
5	15		4
6	18	9	18
7	21		5
8	24	10	20
9	27	3	6
10	30	15	30
11	33	8	16
12	36	9	18
13	39		4
14	42	21	42
15	45		11
16	48	21	42
17	51		6
18	54		20
19	57	14	28
20	60	5	10
21	63		16
22	66	11	22
23	69		12
24	72	6	12
25	75	9	18
26	78	39	78
27	81	4	8
28	84		16
29	87		10
30	90		6
31	93		23
32	96	24	48
33	99		20
34	102	17	34
35	105	26	52
36	108		27
37	111		12
38	114		44
39	117		29
40	120		5
41	123	15	30
42	126	63	126
43	129		12
44	132	9	18
45	135		16
46	138	69	138
47	141		35
48	144	14	28
49	147	9	18
50	150	25	50

　◆ 問題へもどる

　◆ 今週の問題へ

数学の部屋へもどる