質問

はじめまして、山○といいます。現在就職活動中です。どうしても解い
てほしい問題があります。
ある会社の採用試験で出た問題です。いまだに解けません。

問題

ｎ枚のすべて異なる種類のカードを用意する。　i枚のカードを上から取
る。取ったカードの束を　Ａ、残ったカードの束をＢと呼ぶ。Ａの底から
一枚、Ｂの底から一枚、交互に一枚ずつカードをＡとＢより取り新しい束
を作る。最後にＡかＢで余ったカードはそのまま新しい束の上にのせる。
　
　以上の操作でカードの束が最初の状態（順序）に戻るまでには、操作を
何回繰り返せばよいか？

Ｎ＝１００１、ｉ＝１００　として結果はどうなるか？

お返事２００１／８／３１
from=武田

※未解決問題に移しましたが、数教協の仲間の村嶋さんから超級の解答が
寄せられました。感謝！！
さらに、一番下に、この計算をしてくれるＪＡＶＡプログラムが送られて
きました。お楽しみください。

お便り２００１／８／３１
from=村嶋健吾

答は、12025860回です。

（解）
上から数えてx番目のカードは、１回シャッフルすると上からf(x)番目
に移動するものとします。
すると、f(x)は一般に次のようになります。
 f(x)= 2x+n-2i    (1≦x≦i);
     = x-i        (i+1≦x≦n-i);
     = 2x-n-1     (n-i+1≦x≦n).
今、n=1001,i=100 とすると
 f(x)= 2x+801     (1≦x≦100);
     = x-100      (101≦x≦901);
     = 2x-1002    (902≦x≦1001).
です。例えば、
  f(1)=803
です。つまり、1番上にあったカードは１回シャッフルすると、803番目に移
動します。
では、このカードは２回目のシャッフルでどこに移動するでしょうか。
  f(803)=703
です。このようにカードの移動先を順に追っていくと次のようになります。

1,803,703,603,503,403,303,203,103,3,807,707,607,507,407,307,207,107,7,
815,715,615,515,415,315,215,115,15,831,731,631,531,431,331,231,131,31,
863,763,663,563,463,363,263,163,63,927,852,752,652,552,452,352,252,152
,52,905,808,708,608,508,408,308,208,108,8,817,717,617,517,417,317,217,
117,17,835,735,635,535,435,335,235,135,35,871,771,671,571,471,371,271,
171,71,943,884,784,684,584,484,384,284,184,84,969,936,870,770,670,570,
470,370,270,170,70,941,880,780,680,580,480,380,280,180,80,961,920,838,
738,638,538,438,338,238,138,38,877,777,677,577,477,377,277,177,77,955,
908,814,714,614,514,414,314,214,114,14,829,729,629,529,429,329,229,129
,29,859,759,659,559,459,359,259,159,59,919,836,736,636,536,436,336,236
,136,36,873,773,673,573,473,373,273,173,73,947,892,792,692,592,492,392
,292,192,92,985,968,934,866,766,666,566,466,366,266,166,66,933,864,764
,664,564,464,364,264,164,64,929,856,756,656,556,456,356,256,156,56,913
,824,724,624,524,424,324,224,124,24,849,749,649,549,449,349,249,149,49
,899,799,699,599,499,399,299,199,99,999,996,990,978,954,906,810,710,61
0,510,410,310,210,110,10,821,721,621,521,421,321,221,121,21,843,743,64
3,543,443,343,243,143,43,887,787,687,587,487,387,287,187,87,975,948,89
4,794,694,594,494,394,294,194,94,989,976,950,898,798,698,598,498,398,2
98,198,98,997,992,982,962,922,842,742,642,542,442,342,242,142,42,885,7
85,685,585,485,385,285,185,85,971,940,878,778,678,578,478,378,278,178,
78,957,912,822,722,622,522,422,322,222,122,22,845,745,645,545,445,345,
245,145,45,891,791,691,591,491,391,291,191,91,983,964,926,850,750,650,
550,450,350,250,150,50,901,801,701,601,501,401,301,201,101,(1）

最後が(1)になっていますが、１番上に戻ってくるのです。
上に挙げた数字は全部で
    411個
あります。（もちろん1はダブって数えないようにしています。）
これを求めるにはパソコンを使いました。

同様に、次のような数の遷移列が得られます。

2,805,705,605,505,405,305,205,105,5,811,711,611,511,411,311,211,111,11
,823,723,623,523,423,323,223,123,23,847,747,647,547,447,347,247,147,47
,895,795,695,595,495,395,295,195,95,991,980,958,914,826,726,626,526,42
6,326,226,126,26,853,753,653,553,453,353,253,153,53,907,812,712,612,51
2,412,312,212,112,12,825,725,625,525,425,325,225,125,25,851,751,651,55
1,451,351,251,151,51,903,804,704,604,504,404,304,204,104,4,809,709,609
,509,409,309,209,109,9,819,719,619,519,419,319,219,119,19,839,739,639,
539,439,339,239,139,39,879,779,679,579,479,379,279,179,79,959,916,830,
730,630,530,430,330,230,130,30,861,761,661,561,461,361,261,161,61,923,
844,744,644,544,444,344,244,144,44,889,789,689,589,489,389,289,189,89,
979,956,910,818,718,618,518,418,318,218,118,18,837,737,637,537,437,337
,237,137,37,875,775,675,575,475,375,275,175,75,951,900,800,700,600,500
,400,300,200,100,1001,1000,998,994,986,970,938,874,774,674,574,474,374
,274,174,74,949,896,796,696,596,496,396,296,196,96,993,984,966,930,858
,758,658,558,458,358,258,158,58,917,832,732,632,532,432,332,232,132,32
,865,765,665,565,465,365,265,165,65,931,860,760,660,560,460,360,260,16
0,60,921,840,740,640,540,440,340,240,140,40,881,781,681,581,481,381,28
1,181,81,963,924,846,746,646,546,446,346,246,146,46,893,793,693,593,49
3,393,293,193,93,987,972,942,882,782,682,582,482,382,282,182,82,965,92
8,854,754,654,554,454,354,254,154,54,909,816,716,616,516,416,316,216,1
16,16,833,733,633,533,433,333,233,133,33,867,767,667,567,467,367,267,1
67,67,935,868,768,668,568,468,368,268,168,68,937,872,772,672,572,472,3
72,272,172,72,945,888,788,688,588,488,388,288,188,88,977,952,902,802,7
02,602,502,402,302,202,102,(2)
420個

6,813,713,613,513,413,313,213,113,13,827,727,627,527,427,327,227,127,2
7,855,755,655,555,455,355,255,155,55,911,820,720,620,520,420,320,220,1
20,20,841,741,641,541,441,341,241,141,41,883,783,683,583,483,383,283,1
83,83,967,932,862,762,662,562,462,362,262,162,62,925,848,748,648,548,4
48,348,248,148,48,897,797,697,597,497,397,297,197,97,995,988,974,946,8
90,790,690,590,490,390,290,190,90,981,960,918,834,734,634,534,434,334,
234,134,34,869,769,669,569,469,369,269,169,69,939,876,776,676,576,476,
376,276,176,76,953,904,806,706,606,506,406,306,206,106,(6)
140個

28,857,757,657,557,457,357,257,157,57,915,828,728,628,528,428,328,228,
128,(28)
19個

86,973,944,886,786,686,586,486,386,286,186,(86)
11個

以上をまとめますと、
 1の系列　411個
 2の系列　420個
 6の系列　140個
28の系列　 19個
86の系列　 11個
----------------
合計　　 1001個

最後に、411,420,140,19,11の最小公倍数=12025860を求めます。
最小公倍数であれば、すべてのカードが元の位置に戻ってくるのです。

はじめ、12025860という数字をパソコンで直接求めようとしました。
配列変数を用意し、何回シャッフルすると元の配列変数の値に戻るかを求め
ようとしました。時間がかかりすぎ、無理でした。
そこで、上のようにカードの遷移系列を求めるという方法に切り替えたの
です。

お便り２００１／９／２
from=村嶋健吾



【ホームページ閲覧者への注意】
(1)テキストボックスに、遷移系列(循環する数列)が現れます。
これをクリップボード経由で、他のソフトに貼り付けるなどして、
データを分析して下さい。
(2)以前私が与えた関数 f(x) の式は、2i≦ n のときのものです。
2i＞n のときは式が少し変わりますから、注意して下さい。
プログラムは、どちらの場合にも対応しています。