Teman-teman, jangan berharap ada keindahan matematika yang luar biasa atau algoritme yang berguna dalam hidup. Saya menulis hanya karena minat olahraga murni. Saya tertarik dengan masalah yang diterbitkan di sini , yang dihadapi para tahanan Amerika selama menjalani hukuman berat mereka. Menilai dari komentar pada artikel tersebut, hal itu telah membangkitkan minat di komunitas. Saya mengerti bahwa saya tidak melakukannya dengan baik, saya seharusnya memberi orang waktu untuk berpikir sendiri. Namun, saya bertobat, saya adalah orang berdosa, saya tidak bisa menolak. Dan saya memposting keputusan saya di sini. Siapa peduli, selamat datang di kucing. Jika Anda ingin melakukan lebih banyak pemikiran sendiri, jangan membacanya dulu.
Jadi, tugas itu sendiri. Saya akan merumuskannya sedikit lebih jelas daripada di artikel itu sendiri (sayangnya, terjemahannya ada yang sedikit bengkok).
Tombol putar (seperti pada Gambar 1) dapat menunjuk ke bilangan bulat apa pun dari 1 hingga n saat diputar berlawanan arah jarum jam. Hitung mundur dimulai dari 1, kemudian panah berputar secara berurutan (selalu berlawanan arah jarum jam) satu posisi, lalu dua, lalu tiga, dan seterusnya, hingga belokan terakhir dengan posisi n-1. Kami mengumpulkan urutan semua angka yang ditunjukkan oleh panah.
Misalnya, jika n = 12, Anda mendapatkan urutan 1, 2, 4, 7, 11, 4, 10, 5, 1, 10, 8, 7. Dapat dilihat bahwa ada bilangan yang berulang di dalamnya.
Dan untuk n = 8, urutannya adalah 1, 2, 4, 7, 3, 8, 6, 5. Dan tidak ada bilangan yang berulang di dalamnya.
Pertanyaannya adalah, untuk nilai n berapakah angka-angka dalam urutan tersebut tidak diulang?
Dipersembahkan oleh Gary Gordon dan Denise Ozbay, November 2020, Mathematical Horizons.
Mari kita sebut urutan, yang dibangun dalam soal, urutan dari kenop-n . Dan angka, n yang urutan ini tidak mengandung angka berulang, cocok .
Mari kita mulai dengan mendapatkan tip yang sangat serius. Hampir segera jawaban siap pakai. Saya tidak pergi ke penjara Amerika, dan saya tidak tahu apakah komputer tersedia untuk narapidana di sana. Tapi aku punya kuda perang di atas mejaku! Jadi adalah dosa jika tidak menggunakannya. Kami meluncurkan notebook jupyter favorit kami dan memasukkan program kecil:
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
Menjalankan getList (12345) memberikan daftar 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192.
Jadi, sepertinya hanya pangkat dua yang merupakan bilangan valid, dan tidak ada lagi. Itu hanya tinggal membuktikannya. Lebih tepatnya, dua pernyataan harus dibuktikan:
1) Pangkat dua adalah bilangan yang cocok.
2) Bilangan apa pun yang bukan pangkat dua tidak cocok.
Pertama, mari kita lihat dari mana bilangan-bilangan berulang itu berasal dari urutan n-dial.
Urutannya dimulai dari 1. Kenaikannya pada langkah pertama juga sama dengan 1, dan kemudian dengan setiap langkahnya bertambah 1. Sisa pembagian dengan n diambil sebagai hasilnya. Selain itu, jika sisanya adalah nol, maka hasilnya diasumsikan sama dengan n. Mari kita coba membuat barisan seperti itu untuk beberapa bilangan n yang tidak terlalu besar. Misalnya 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
Kita melihat bahwa dua pasangan bertepatan: s (1) dan s (4), dan s (3) dan s (6). Selain itu, jika kita mengambil nilai bukan modulo, perbedaan antara elemen yang lebih besar dan lebih kecil dari kedua pasangan adalah kelipatan 6. Itu, secara umum, cukup bisa dimengerti. Nilai akhir diambil modulo n. Dan jika, sebelum mengambil modulus, angkanya berbeda n (atau kelipatan n), maka nilai akhirnya akan sama.
Di sisi lain, karena kenaikan yang kita miliki di setiap langkah meningkat 1. Dan jelas bahwa perbedaan di atas sama dengan jumlah dari beberapa angka yang berurutan. Misalnya, untuk pasangan s (1), s (4):
7 = 1 + (1 + 2 + 3)
Dan untuk pasangan s (3), s (6):
16 = 4 + (3 + 4 + 5)
Untuk yang pertama selisihnya adalah 6 untuk pasangannya, dan 12 untuk yang kedua.
Jadi, kita sampai pada kesimpulan penting:
Jika bilangan yang sama muncul dalam urutan n-dial, maka n atau kelipatannya dapat direpresentasikan sebagai penjumlahan dari beberapa bilangan yang berurutan, yang terbesar tidak melebihi bilangan n-1.
Pertama, kita membuktikan pernyataan bantu:
Bilangan apa pun yang bukan pangkat dua dapat direpresentasikan sebagai jumlah dari bilangan yang berurutan. Tidak ada pangkat dua yang dapat diwakili oleh jumlah bilangan yang berurutan.
Mari kita pikirkan tentang bagaimana merepresentasikan beberapa angka secara umum sebagai jumlah dari angka-angka yang berurutan. Untuk yang ganjil, ini cukup sederhana. Jika A ganjil, maka dapat diwakili oleh pasangan:
A = [A / 2] + ([A / 2] + 1), di mana [] berarti bagian bilangan bulat dari bilangan tersebut.
Misalnya 11 = [11/2] + ([11/2] + 1) = 5 + (5 + 1) = 5 + 6.
Hanya saja untuk kelipatan 3. Jika A adalah kelipatan 3, maka:
A = (A / 3 - 1) + A / 3 + (A / 3 + 1).
Demikian pula, jika A adalah kelipatan 5:
A = (A / 5 - 2) + (A / 5 - 1) + A / 5 + (A / 5 + 1) + (A / 5 + 2).
Dan secara umum, jika bilangan A memiliki pembagi ganjil B, bilangan tersebut dapat direpresentasikan sebagai penjumlahan bilangan berurutan B, dan bilangan A / B tepat di tengahnya.
Contoh:
27 = 3 * 9. Karenanya 27 = (9-1) + 9 + (9 + 1) = 8 + 9 + 10,50
= 5 * 10. Karenanya 50 = (10-2) + (10-1) +10 + (10 + 1) + (10 + 2) = 8 + 9 + 10 + 11 + 12.
Kebalikannya juga jelas. Jika sebuah bilangan dapat direpresentasikan sebagai jumlah ganjil dari bilangan berurutan, maka ia memiliki pembagi ganjil, dan representasi itu sendiri memiliki bentuk yang dijelaskan di atas. Oleh karena itu, pangkat dua tidak bisa menjadi jumlah ganjil dari bilangan berurutan , karena tidak memiliki pembagi ganjil.
Tetapi bagaimana dengan jumlah bilangan genap dari bilangan yang berurutan? Jumlah dari dua angka yang berurutan selalu ganjil. Ini semoga jelas. Jumlah empat dapat dianggap sebagai jumlah dari dua pasang, yang masing-masing ganjil. Jadi jumlah empatnya genap. Jumlah enam lagi ganjil, jumlah delapan genap, dan seterusnya. Itu. jumlah dari bilangan genap dari bilangan yang berurutan adalah genap jika angkanya adalah kelipatan 4, dan ganjil jika hanya kelipatan 2.
Misalkan bilangan genap A adalah jumlah dari 4 * k bilangan yang berurutan. Untuk kesederhanaan, misalkan k = 1, untuk k besar alasannya sepenuhnya analog:
A = a + (a + 1) + (a + 2) + (a + 3) = 4 * a + 6.
Bagilah persamaan ini dengan 2 :
A / 2 = (4 * a + 6) / 2 = 2 * a + 3 = (a + 1) + (a + 2).
Itu. sekali lagi kita mendapatkan jumlah angka yang berurutan.
Oleh karena itu, jika untuk bilangan genap A ada representasi berupa penjumlahan bilangan genap bilangan berurutan, maka ada representasi berupa penjumlahan bilangan berurutan untuk A / 2 .
Misalnya:
26 = 5 + 6 + 7 + 8. Maka 26/2 = 13 = (5 + 1) + (5 + 2) = 6 + 7.
Misalkan untuk pangkat dua ada representasi berupa penjumlahan bilangan genap bilangan berurutan (tidak ada representasi bilangan ganjil untuk itu seperti gambar di atas). Kemudian ada representasi berupa penjumlahan bilangan berurutan untuk derajat N-1. Dan jumlah suku di dalamnya juga genap. Dengan induksi, hal yang sama dapat dikatakan tentang derajat N-2 dan tentang derajat N-3 dan, secara umum, tentang derajat apa pun yang kurang dari N. Tetapi tidak ada representasi dalam bentuk jumlah bilangan berurutan untuk bilangan tersebut. 4, yang mudah dilihat. Oleh karena itu, tidak ada pangkat dua yang dapat direpresentasikan sebagai jumlah angka yang berurutan .
Di sisi lain, bilangan apa pun yang bukan merupakan pangkat dua dapat direpresentasikan sebagai jumlah bilangan yang berurutan. Jika bilangan ini ganjil, dapat direpresentasikan sebagai pasangan. Jika bilangan bulat dan bukan pangkat dua, maka ia memiliki setidaknya satu pembagi ganjil. Dan dapat direpresentasikan melalui itu.
Pernyataan tambahan terbukti.
Pertimbangkan seluruh urutan n-dial.
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)
Biarkan n menjadi pangkat dua. Kemudian 2 * n, 4 * n, 8 * n, dll., Juga merupakan pangkat dua. Dan sebagai jumlah dari angka-angka yang berurutan, mereka tidak dapat direpresentasikan. Yang dapat direpresentasikan adalah 3 * n, 5 * n, 6 * n, 7 * n, 9 * n, dll. Itu. bilangan m * n harus memiliki setidaknya satu pembagi ganjil. Namun, bahkan yang terkecil dari kelipatan ini, 3 * n, harus direpresentasikan sebagai
(n - 1) + n + (n + 1).
Tidak ada representasi lain dari angka 3 * n. Karena n sebagai pangkat dua tidak memiliki representasi sama sekali (lihat pernyataan bantu). Tetapi suku-suku dalam jumlah ini tidak boleh melebihi angka n - 1. Oleh karena itu, 3 * n sebagai perbedaan tidak akan pernah muncul. Untuk kelipatan lainnya, alasannya sama persis. Tentu saja, baik n maupun 2 * n tidak akan muncul sebagai perbedaan, sebagai pangkat dua. Jadi pangkat dua apa pun adalah bilangan yang cocok.
Pernyataan (1) terbukti.
Sekarang biarlah tidak menjadi kekuatan dua. Itu. direpresentasikan sebagai jumlah angka yang berurutan. Perbedaan antara anggota pertama dan terakhir dari urutan (sebelum mengambil modul dengan n) adalah:
d = 1 + 2 + 3 +… + (n-1).
Dan perbedaan antara anggota urutan n-dial (sebelum mengambil modul) adalah jumlah parsial dari rangkaian ini. Jika n dapat direpresentasikan sebagai jumlah dari bilangan yang berurutan, maka kemungkinan bilangan terbesar yang membentuk jumlah tersebut adalah
[n / 2] dan [n / 2] + 1. ([] adalah bagian bilangan bulat dari sebuah bilangan)
Lainnya varian dari jumlah seperti itu terdiri dari angka yang lebih kecil ... Ini berarti bahwa anggota barisan kenop-n, dengan selisih sebelum mengambil modulus sama dengan n, pasti akan ditemukan. Dan setelah mengambil modul, mereka akan memberikan nomor yang cocok. Itu. setiap n yang bukan merupakan pangkat dua, dan oleh karena itu dapat direpresentasikan sebagai jumlah bilangan yang berurutan, bukanlah bilangan yang sesuai.
Pernyataan (2) terbukti.
Secara total, tugas selesai sepenuhnya. Nomor yang cocok adalah pangkat dua dan bukan yang lain. Untuk kebebasan dengan hati nurani yang bersih !!!
Moral dari dongeng ini mungkin hanya satu. Teman-teman, bahkan jika Anda melakukan matematika murni, jangan abaikan eksperimen komputasi. Ya, eksperimen semacam itu tidak membuktikan apa-apa. Namun, mereka dapat memberikan tebakan yang beralasan. Meski mungkin tidak sesederhana di sini. Dan membuktikan biasanya jauh lebih mudah daripada menebak-nebak. Saya akan senang jika seseorang menemukan presentasi ini bermanfaat dan menarik.