|
uchinyan |
|
お詫び及び修正
ごめんなさい。証明の一部に誤りがありました。 提示されている実例の構成法は，m-1 が素数の場合にだけ有効，です。 m-1 が素数でない場合は，部分周期が発生しうまくいきません。 お詫びして修正します。 #41739のJママさんの発展的な考察＝問題への #41740の私の一般的な解， N = k = m(m-1) + 1 = (m-1)m + 1 の証明を試みてみました。 少し分かりづらいかもという気もしますが，#41740の例を見ながらお読みください。 まず，m = 1 の場合には他の人と会わないので，m >= 2 とします。 また，k = 1，N = m，という自明な解がありますが，これは除きます。 つまり，k >= 2 とします。 １日目に 1 〜 m が来るとします。 ２日目は，N を最小にするので１日目の１人，1 とします，が来て，同じ人とは１度しか会えないので新たな人が m-1 人来ます。 ３日目以降は，同様に，１日目と２日目から高々１人ずつ来て，残りは新たな人が来る，と考えられます。 このとき，1 は３日目以降の新たな人とも会わないといけないので，３日目にそうなるとしても一般性を失いません。 しかし，既に 1 と会っている人は来られないので，３日目は，1 と新たな m-1 人となります。 こうした日が 1 がすべての人と会うまで続くので，１日目を含めて a 日続いたとして， N = (m-1)a + 1 人 になります。ここで，最後の + 1 は 1 自身の人数，つまり１人，です。 次に，2 について考えます。 2 も 1 と同様に１日目以外の (m-1)(a-1) 人と１度ずつ会わなければなりません。 これは，２度同じ人とは会えないので，1 と同様に，１日に m-1 人ずつ a-1 日で合うことになります。 ここで，a < m だとすると，２日目の 1 以外の m-1 人を a-1 日に振り分けると， 鳩ノ巣原理により，必ず，２日目に会っている２人が再び会ってしまう日が存在します。 これは許されないので，a >= m でなければなりません。そこで， N = (m-1)a + 1 >= (m-1)m + 1 人 になります。このとき，１日目に来た 3 〜 m も同様で，１日に m-1 人ずつ a-1 日で会うことになります。 したがって，全体の日数は，1 〜 m に対して a-1 日ずつで，１日目も追加して， k = (a-1)m + 1 >= (m-1)m + 1 日 です。 今は，N を最小にしたいので，N = (m-1)m + 1，a = m，となることが理想です。 そこで，このときは， N = k = (m-1)m + 1 になります。 後，残された問題は，実際にこうなる例を作れるかどうかです。 これは，m-1 が素数の場合には，#41740の m = 4 の例のようにすれば可能です。 つまり， 1 日目：1 〜 m 2 日目：1 a(1,1) a(1,2) a(1,3) ... a(1,m-1) 3 日目：1 a(2,1) a(2,2) a(2,3) ..., a(2,m-1) ．．． m 日目：1 a(m-1,1) a(m-1,2) a(m-1,3) ... a(m-1,m-1) (m-1)+2 日目：2 a(1,1) a(2,1) a(3,1) ... a(m-1,1) (m-1)+3 日目：2 a(1,2) a(2,2) a(3,2) ... a(m-1,2) ．．． 2(m-1)+1 日目：2 a(1,m-1) a(2,m-1) a(3,m-1) ... a(m-1,m-1) 2(m-1)+2 日目：3 a(1,1) a(2,2) a(3,3) ... a(m-1,m-1) 2(m-1)+3 日目：3 a(1,2) a(2,3) a(3,4) ... a(m-1,1) ．．． 3(m-1)+1 日目：3 a(1,m-1) a(2,1) a(3,2) ... a(m-1,m-2) 3(m-1)+2 日目：4 a(1,1) a(2,3) a(3,5) ... a(m-1,m-2) 3(m-1)+3 日目：4 a(1,2) a(2,4) a(3,6) ... a(m-1,m-1) ．．． 4(m-1)+1 日目：4 a(1,m-1) a(2,2) a(3,4) ... a(m-1,m-3) ．．． (m-1)(m-1)+2 日目：m a(1,1) a(2,m-1) a(3,m-2) ... a(m-1,1) (m-1)(m-1)+3 日目：m a(1,2) a(2,1) a(3,m-1) ... a(m-1,m-2) ．．． m(m-1)+1 日目：m a(1,m-1) a(2,m-2) a(3,m-3) ... a(m-1,1) 要するに，縦方向のものを 0，1，2，...，m-2 ずつずらしてクルクル循環的に横方向に並べる感じです。 m-1 が素数の場合には，1，2，...，m-2 と m-1 が互いに素なので，うまく散らばって例を作れます。 しかし，m-1 が素数でない場合には，1，2，...，m-2 の中に m-1 と互いに素でないものがあり， 部分周期が発生しうまく例を作れません。 ただ，これはこの構成法が失敗するだけで，実例が存在するかしないかはよく分かっていません。 以上より，結局，一般に， N = (m-1)a + 1 >= (m-1)m + 1，k = (a-1)m + 1 >= (m-1)m + 1 がいえ，特に，m-1 が素数の場合には， N = k = (m-1)m + 1 になります。 m-1 が素数でない場合で不等式の等号が成立するかどうかは，実例が存在するかどうかにかかっています。 別掲載で，m = 6 と m = 5 の場合を載せておきます。 |
|
ネコの住む家
4月28日（月） 11:16:55
41745 |