みんな、人生で卓越した数学的美しさや有用なアルゴリズムを期待しないでください。私は純粋なスポーツの興味から書いています。私はここで発表された問題に興味を持っていました 。それはアメリカ人の囚人が彼らの巨大な文章を離れている間でした。記事へのコメントから判断すると、すでにコミュニティへの関心が高まっています。私はあまりうまくいっていないことを理解しています、私は人々に自分で考える時間を与えるべきでした。しかし、私は悔い改め、罪人であり、抵抗することはできません。そして、私はここに私の決定を投稿します。誰が気にする、猫へようこそ。自分でもう少し考えたい場合は、まだ読んではいけません。
したがって、タスク自体。記事自体よりも少し明確に定式化し ます(ああ、翻訳は少し曲がっています)。
ダイヤル(図1のように)は、反時計回りに回転すると、1からnまでの任意の整数を指すことができます。カウントダウンは1から始まり、矢印は1つの位置、次に2つ、次に3つというように、最後にn-1の位置まで順番に(常に反時計回りに)回転します。矢印が指すすべての番号のシーケンスを収集します。
たとえば、n = 12の場合、シーケンス1、2、4、7、11、4、10、5、1、10、8、7が得られます。繰り返し番号が含まれていることがわかります。
また、n = 8の場合、シーケンスは1、2、4、7、3、8、6、5になります。繰り返し番号はありません。
問題は、nのどの値に対して、シーケンス内の数値が繰り返されないのかということです。
ゲイリーゴードンとデニスオズベイ、2020年11月、数学の地平線によって提示されました。
問題で構成されているシーケンスをnダイヤルのシーケンスと呼びましょう 。そして、このシーケンスに繰り返し番号が含まれていない番号 nが 適しています。
非常に深刻なヒントを得ることから始めましょう。ほぼ即座に既成の答え。私はアメリカの刑務所に行きませんでした、そしてそこでの囚人がコンピューターを利用できるかどうかわかりません。しかし、私は私のテーブルに私の戦火の馬を持っています!ですから、それを使わないのは罪です。お気に入りのjupyterノートブックを起動し、小さなプログラムに入ります。
def getSeq(n): # n-
lst=[]
s=1 #
d=1 #
for i in range(0, n):
lst.append(s)
s=(s+d) % n
if s==0:
s=n
d=d+1 # 1
return lst
def testSeq(lst): #
if len(set(lst)) == len(lst):
return True
return False
def getList(n): # , 2 n
lst=[]
for i in range(2, n):
if testSeq(getSeq(i)):
lst.append(i)
return lst
getList(12345)を実行すると、2、4、8、16、32、64、128、256、512、1024、2048、4096、8192のリストが表示されます。
したがって、2の累乗のみが有効な数値である可能性が非常に高くなります。何もありません。それを証明することだけが残っています。より正確には、2つのステートメントを証明する必要があります
。1)2の累乗は適切な数です。
2)2の累乗でない数値は適切ではありません。
まず、繰り返し番号がnダイヤルシーケンスのどこから来ているかを見てみましょう。
シーケンスは1から始まります。最初のステップでの増分も1に等しく、各ステップで1ずつ増加します。結果としてnによる除算の余りが取られます。さらに、余りがゼロの場合、結果はnに等しいと見なされます。それほど大きくない数nに対してそのようなシーケンスを構築してみましょう。たとえば、n = 6:
s(1)= 1(mod 6)= 1
s(2)= 1 + 1(mod 6)= 2
s(3)= 2 + 2(mod 6)= 4
s(4) = 4 + 3(mod 6)= 7(mod 6)= 1
s(5)= 7 + 4(mod 6)= 11(mod 6)= 1 + 4(mod 6)= 5
s(6)= 11 + 5(mod 6)= 16(mod 6)= 5 + 5(mod 6)= 4
s(1)とs(4)、およびs(3)とs(6)の2つのペアが一致していることがわかります。さらに、モジュロではない値をとると、両方のペアの大きい要素と小さい要素の差は6の倍数になります。これは一般的に非常に理解できます。最終値はnを法として取得されます。そして、モジュラスを取る前に、数値がn(またはnの倍数)だけ異なる場合、最終的な値は一致します。
一方、各ステップでの増分は1ずつ増加するため、上記の差がいくつかの連続する数値の合計に等しいことは明らかです。たとえば、ペアs(1)の場合、s(4):
7 = 1 +(1 + 2 + 3)
およびペアs(3)の場合、s(6):
16 = 4 +(3 + 4 + 5)
最初の違いは、ペアが6、2番目が12です。
したがって、重要な結論に達します。
一致する番号がnダイヤルのシーケンスに表示される場合、nまたはその倍数は、いくつかの連続した番号の合計として表すことができ、最大のものは番号n-1を超えません。
まず、補助的なステートメントを証明し
ます。2の累乗ではない数値は、連続する数値の合計として表すことができます。 2の累乗は、連続する数の合計で表すことはできません。
ある数を連続した数の合計として一般的に表す方法を考えてみましょう。奇妙なものの場合、これは非常に簡単です。 Aが奇数の場合、
A = [A / 2] +([A / 2] + 1)のペアで表すことができます 。ここで、[]は数値の整数部分を意味します。
たとえば、11 = [11/2] +([11/2] + 1)= 5 +(5 + 1)= 5 +6です。
Aが3の倍数の場合、次のようになります
。A=(A / 3-1)+ A / 3 +(A / 3 + 1)。
同様に、Aが5の倍数の場合:
A =(A / 5-2)+(A / 5-1)+ A / 5 +(A / 5 + 1)+(A / 5 + 2)。
そして、一般に 、数Aが奇数の約数Bを持っている場合、それはBの連続する数の合計として表すことができ、数A / Bはちょうど真ん中にあります。
例:
27 = 3 * 9。したがって、27 =(9-1)+ 9 +(9 + 1)= 8 + 9 + 10.50
= 5 * 10。したがって、50 =(10-2)+(10-1)+10 +(10 + 1)+(10 + 2)= 8 + 9 + 10 + 11 +12。
逆も明らかです。数が奇数の連続する数の合計として表現できる場合、その数は奇数の約数を持ち、表現自体は上記の形式になります。したがって、2の 累乗は、奇数の除数がないため、奇数の連続する数の合計にすることはできません。
しかし、偶数の連続した数の合計はどうですか? 2つの連続する数値の合計は常に奇数です。これはうまくいけば明らかです。 4つの合計は、それぞれが奇数である2つのペアの合計と考えることができます。したがって、4つの合計は偶数です。 6の合計は再び奇数、8の合計は偶数などです。それら。偶数の連続する数の合計は、それらの数が4の倍数である場合は偶数であり、2の倍数である場合は奇数です。
偶数Aを4 * k個の連続した数の合計とします。簡単にするために、k = 1とします。大きなkの場合、推論は完全に類似しています
。A= a +(a + 1)+(a + 2)+(a + 3)= 4 * a +6。
この等式を2で割ります。 :
A / 2 =(4 * a + 6)/ 2 = 2 * a + 3 =(a + 1)+(a + 2)。
それら。ここでも、連続した数値の合計を取得します。
したがって、 偶数Aの場合、偶数の連続数の合計の形式の表現がある場合、A / 2には、連続数の合計の形式の表現が存在します。
例:
26 = 5 + 6 + 7 +8。したがって、26/2 = 13 =(5 + 1)+(5 + 2)= 6 +7。
2のN乗に対して、偶数の連続した数の合計の形式の表現があると仮定します(上記のように奇数の形式の表現はありません)。次に、次数N-1の連続数の合計の形式で表現があります。そして、その中の用語の数も均等です。誘導により、次数N-2と次数N-3について、そして一般にN未満の任意の次数について同じことが言えます。しかし、数の連続数の合計の形での表現はありません。 4、見やすいです。したがって、 2の累乗を連続した数の合計として表すことはできません。
一方、2の累乗ではない数値は、連続する数値の合計として表すことができます。この数が奇数の場合、ペアとして表すことができます。偶数で2の累乗ではない場合、少なくとも1つの奇数の約数があります。そしてそれを通して表現可能です。
補助ステートメントが証明されます。
nダイヤルシーケンス全体を検討してください。
s(1)= 1(mod n)
s(2)= 1 + 1(mod n)
s(3)= 2 + 2(mod n)
s(4)= 4 + 3(mod n)
…
s(n )= s(n-1)+ n-1(mod n)
nを2の累乗とします。その場合、2 * n、4 * n、8 * nなども2の累乗です。そして、連続した数の合計として、それらは表現できません。表現可能なのは、3 * n、5 * n、6 * n、7 * n、9 * nなどです。それら。数m * nには、少なくとも1つの奇数の約数が必要です。ただし、これらの倍数の最小値である3 * nでさえ、
(n-1)+ n +(n + 1)として表す必要があります 。
数3 * nの他の表現はありません。 2の累乗としてのnの場合、表現はまったくありません(補助ステートメントを参照)。ただし、この合計の項は、数n-1を超えてはなりません。したがって、差として3 * nが表示されることはありません。他の倍数の場合、理由はまったく同じです。もちろん、nも2 * nも、2の累乗としての違いとしては表示されません。したがって、2の累乗は適切な数です。
ステートメント(1)が証明されます。
ここで、nを2の累乗にしないでください。それら。連続した数の合計として表すことができます。シーケンスの最初のメンバーと最後のメンバーの違い(モジュールをnで取得する前)は、
d = 1 + 2 + 3 +…+(n-1)になります。
また、(モジュールを取得する前の)nダイヤルシーケンスのメンバー間の違いは、このシリーズの部分的な合計になります。 nが連続する数の合計として表現できる場合、そのような合計を構成する可能な最大の数は
[n / 2]および[n / 2] + 1です。([]は数の整数部分です)
その他すべてそのような合計の変形は、さらに小さな数で構成されています...これは、nに等しいモジュラスを取る前に差がある、nダイヤルのシーケンスのメンバーが確実に見つかることを意味します。そして、モジュールを取った後、彼らは一致する番号を与えます。それら。 2の累乗ではないため、連続する数の合計として表すことができるnは、適切な数ではありません。
ステートメント(2)が証明されます。
全体として、タスクは完全に解決されます。適切な数は2の累乗であり、他の累乗ではありません。明確な良心を持って自由へ!!!
この寓話の教訓はおそらく1つだけです。純粋数学をしていても、計算実験を怠らないでください。はい、そのような実験は何も証明しません。しかし、彼らは十分に根拠のある推測をすることができます。ここほど単純ではないかもしれませんが。そして、証明は通常、推測よりもはるかに簡単です。誰かがこのプレゼンテーションが有用で面白いと思ったら嬉しいです。