1 den 50 ye kadar olan tam sayıları öyle 2 gruba ayırın ki gruplardaki sayıların karekökleri toplamı birbirine en yakın büyüklükte olsun?

Question

2.4.6.8.10.12.14.16.18.19.21.23.25.26.30.31.33.34.35.38.42.44.45.47.49 karekökleri toplamı = 119.517

1.3.5.7.9.11.13.15.17.20.22.24.27.28.29.32.36.37.39.40.41.43.46.48.50 karekökleri toplamı =119.517

bilgisayar kullanmadan 15 dk. da bulundu.

Comments

aradaki fark 0.0001 dir.

---

Merhaba, Matkafasi'na hoş geldin. Sitede soru sorarken dikkat edilmesi gereken pek çok kural var. Bunlardan en önemlilerinden birisi, soru soran kişinin yazdığı soru hakkında kendi denemelerini ve düşündüklerini yazması kuralı. Bu kuralın pek çok nedeni var. Bu konuda lütfen şuradaki yorumu okuyunuz. Genel kurallar hakkında da lütfen şuraya bakınız.

Kısacası: Neler düşündüğünüzü ve neleri denediğinizi yazmanızı istiyoruz.

Önemli anımsatma: Genel olarak kurallara uygun sorulmuş sorular yanıt bulmakta.

Bu arada kategorinizi değiştirin.

---

Çözüm uzayı 2^50 = 1125899906842624 adet olduğu için kaba kuvvet ile çözmek çok olanaklı değil.

Çalıştığımız küme reel sayılar kümesi olduğundan klasik "subset sum" (altküme toplamları) dinamik programlama metodunu uygulamak da çok uygun görünmüyor. Ancak eğer bizden farkın herhangi bir değerden küçük olduğu herhangi bir çözüm istenilseydi; reel sayı olan karekökler, istenilen hassasiyet elde edilecek şekilde bir tam sayı ile çarpılıp yuvarlayarak tam sayı haline getirerek, tam sayılar kümesinde çalışmak mümkün olurdu.  Bu soru için minimum değer 10^(-13) seviyesinde olduğu için, bu cevaba tam sayıya yuvarlanmış subset sum metoduyla yaklaşmak için en azından 10^15 adet eleman gerekmekte.  Bu metod da uygun değil. 

Uygun bir çözüm olarak; 1 den 50ye kadar olan sayılar kümesini iki eşit parçaya ayırarak her iki kümenin olası tüm karekök toplamlarını bulabiliriz. Burada çözüm uzayı iki adet 2^25 = 33554432 olmakta.

Elimizdeki iki adet karekök toplamı kümesini, küçükten büyüğe sıralaylım. Birincinin tüm elemanlarını sırayla ele alarak, ikincideki en yakın sayıyı "Binary search" ile hızlıca bulmak mümkün. Her yeni bulunan ikili farkını o ana kadarki en küçük ile karşılaştırarak, tüm uzaydaki olası en küçük farkı bulabiliriz.

Bir optmizasyon olarak;  2^25 olan çözüm uzayı yerine,  simetrik sonuçlar olduğundan, bir seviye aşağıda yani 2^24 = 16777216 adedini hesaplamak yetecektir.

Bir küçük optmizasyon daha, karekökleri tam sayı olan (1,4,9,16...) sayıları ayırarak yukarıdaki işlemleri yapıp, sonradan  çözümün içine dahil edilebilir. 

Tam sonuç:

[1, 2, 3, 4, 5, 6, 9, 10, 11, 14, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 29, 32, 34, 35, 39, 40, 42, 50]

[7, 8, 12, 13, 15, 16, 25, 27, 30, 31, 33, 36, 37, 38, 41, 43, 44, 45, 46, 47, 48, 49] 

Karekoklerin toplami= [119.51790030176032, 119.51790030176048]

Fark = 1.5631940186722204e-13

(Python-3 de normal laptop ile 12 dakika )

Gözlemlerime göre bulunan farkın değeri, kullandığımız sayı adedi arttığı oranda 2 ile bölünerek küçülmekte. Örneğin eğer 50 değil de 55 sayı olsaydı, yukarıdaki farktan 2^5 = 32 kat daha küçük mertebede bir fark bekleyebilirdik. Bu gözlem istatistiki beklentiye de uygun.

 

Answer 1

Mathematica ile (Rastgele Arama yontemi ) ben su  ikiliyi buldum. Bundan daha kucuk ikili bulmak mumkun.

Daha hizli versiyon ile da kucuk fark buldum..

3. deneme:

list = Table[Partition[RandomSample[Range@50], 25], 20000000];

list2 = Abs[(Total[Sqrt[N@#1] - Sqrt[N@#2]]) & @@@ list];


min = Min@list2 // DecimalForm

0.000000471679

Sort /@ Extract[list, First@Ordering[list2, 1]]
{{3, 5, 7, 8, 9, 12, 13, 16, 18, 19, 22, 23, 24, 25, 28, 29, 35, 36,
39, 40, 41, 42, 43, 44, 46}, {1, 2, 4, 6, 10, 11, 14, 15, 17, 20,
21, 26, 27, 30, 31, 32, 33, 34, 37, 38, 45, 47, 48, 49, 50}}


2. deneme:

list = Table[Partition[RandomSample[Range@50], 25], 5000000];
list2 = Abs[(Total[Sqrt[N@#1] - Sqrt[N@#2]]) & @@@ list];
min = Min@list2 // DecimalForm

0.000000866643

Sort /@ Extract[list, First@Ordering[list2, 1]]
{{1, 5, 6, 9, 10, 12, 13, 14, 16, 18, 20, 23, 25, 26, 28, 30, 32, 34,
40, 41, 43, 45, 48, 49, 50}, {2, 3, 4, 7, 8, 11, 15, 17, 19, 21, 22,
24, 27, 29, 31, 33, 35, 36, 37, 38, 39, 42, 44, 46, 47}}


 

Ilk deneme:

list2 = Table[Partition[RandomSample[Range@50, 50], 25], 500000];
list3 = Abs[(Total@Sqrt[#1] - Total@Sqrt[#2]) & @@@ list2 // N];

min = Min@list3 // DecimalForm
0.00000988892
Sort /@ Extract[list2, First@Ordering[list3, 1]]

{{1, 4, 6, 7, 8, 9, 13, 14, 16, 18, 23, 24, 28, 30, 32, 33, 35, 36,
37, 39, 42, 44, 46, 48, 50}, {2, 3, 5, 10, 11, 12, 15, 17, 19, 20,
21, 22, 25, 26, 27, 29, 31, 34, 38, 40, 41, 43, 45, 47, 49}}


 

Kolay Gelsin..