題目
有n位數學家圍著一張圓桌,分別坐在依順時針方向標示著1, 2, 3, …, n的座位上。在休息後,他們再度圍著圓桌而坐,每個座位坐一人,這些數學家發現有一個正整數a使得
(1)對於每個k,每位數學家在休息前原先坐在座號k的人,在休息後坐在座號ka(其中座號\(i + n\)的座號視為i);
(2)在休息後任何兩位數學家之間的數學家的人數,不論按順時針方向數、或逆時針方向數,都與休息前兩人之間的數學家的人數都不同。
試求在\(1 < n < 1000\)中總共有多少個滿足條件的n。
解:
對於任意正整數n,令\(a = 1,2,3,…,(n – 1)\)(其餘大於n的數只要餘數同a的重坐後順序是跟a一樣的)
而無論n為何,\((a,n) = 1\),否則座位會重複
設任意兩數學家原本的座號為x,y,
訂此兩人間的人數為\(|x – y|\)(順時針方向)
\(|x – y| = 1,2,3,…,(n – 1)\)
而重坐後的兩人間的人數則為\(a|x – y| – mn\)(其中m為使\(0 < a|x – y| – mn < n\)的最大整數)
依照題意可知
重坐後需滿足
(1) \(a|x – y| – mn \ne |x – y|\)\( \Rightarrow (a – 1)|x – y| \ne mn\)
(2) \(a|x – y| – mn \ne n – |x – y|\)\( \Rightarrow (a + 1)|x – y| \ne mn\)(逆時針方向)
若n為偶數,則∵\((a,n) = 1\),∴a必為奇數
故\((a – 1)\)必為偶數,令\((a – 1) = 2t\)
設n=2k,則k必為1,2,…,(n-1)其中一個數
故當\(|x – y| = k\)時,\((a – 1)|x – y| = 2kt = tn\)不符合(1)之條件,
故所有偶數皆不合
若n為奇數,則\(a = 2\)時,
\((a – 1)|x – y|\)
\( = |x – y| = 1,2,3,…,(n – 1)\)
此時無論m為何,\((a – 1)|x – y| \ne mn\)
即所有奇數皆滿足(1)
若3|n,令n=3p,同理p必為1,2,…,(n-1)其中一個數
∵\((a,n) = 1\),∴\((a – 1)\)與\((a + 1)\)必有一個為3的倍數,設為3q
當\(|x – y| = p\)時,\(3q|x – y| = 3pq = qn\)又與(1)(2)其中之一不合
故n必不為3的倍數
其餘的奇數只要不是3的倍數,在\(a = 2\)時皆可以滿足(1)(2)的條件
1<n<1000中為奇數且不為3的倍數者共有499-167=332個