mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2022-04-02, 12:24   #1
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

3×5×569 Posts
Default April 2022

https://research.ibm.com/haifa/ponde...April2022.html
Xyzzy is offline   Reply With Quote
Old 2022-04-04, 01:44   #2
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

32·11 Posts
Default

For trying n=4
I get this optimal solution:

x = [0.825694, -0.0756939 , -0.5 , -0.25]
y = [-0.0756939, -0.25, -0.5 , 0.825694]

f(x,y)= 6.74306

Can anyone confirm if there is other optimal results for n=4 ?

Last fiddled with by Kebbaj on 2022-04-04 at 02:09
Kebbaj is offline   Reply With Quote
Old 2022-04-04, 02:20   #3
uau
 
Jan 2017

23×19 Posts
Default

Quote:
Originally Posted by Kebbaj View Post
I get this optimal solution:
Why do you call that "optimal"? It does not meet the criterion.
uau is offline   Reply With Quote
Old 2022-04-04, 02:38   #4
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

32×11 Posts
Default

Quote:
Originally Posted by uau View Post
Why do you call that "optimal"? It does not meet the criterion.
Whos criterion you want to say? f(x,y)=4.?
Precisely for n=4, it seems to me that f has the optimum at 6.74. Am I wrong or I don't understand well the question?

Last fiddled with by Kebbaj on 2022-04-04 at 03:01
Kebbaj is offline   Reply With Quote
Old 2022-04-04, 03:27   #5
uau
 
Jan 2017

23·19 Posts
Default

Quote:
Originally Posted by Kebbaj View Post
Whos criterion you want to say? f(x,y)=4.?
Precisely for n=4, it seems to me that f has the optimum at 6.74. Am I wrong or I don't understand well the question?
You're wrong.
uau is offline   Reply With Quote
Old 2022-04-04, 07:55   #6
tgan
 
Jul 2015

3610 Posts
Default

Quote:
Originally Posted by Kebbaj View Post
Whos criterion you want to say? f(x,y)=4.?
Precisely for n=4, it seems to me that f has the optimum at 6.74. Am I wrong or I don't understand well the question?
Reda i checked your Solution for n = 4 and getting the same results as you.
i did not search for optimal just checked that per my understanding it meets the constraints and calculate f(x,y)

Last fiddled with by tgan on 2022-04-04 at 07:58 Reason: fix the logic
tgan is offline   Reply With Quote
Old 2022-05-29, 12:16   #7
Dieter
 
Oct 2017

7×19 Posts
Default April 2022

Did anyone else find the excellent solution of Anders Kaseorg?
How do you find something like that?
Dieter is offline   Reply With Quote
Old 2022-06-04, 19:54   #8
uau
 
Jan 2017

23×19 Posts
Default

Note that you can permute the order of x_i arbitrarily if you also permute y_i the same way.
Take the example solution given in the problem statement and order the x_i in ascending order:

x = [-0.3688259, -0.36163773, -0.3562014, 0.45420977, 0.63245526]
y = [-0.05259805, -0.04540969, -0.03997346, 0.77043701, -0.6324558]

Note that the last element in each is about the negative of the other.
Also,
y-x = [ 0.31622785, 0.31622804, 0.31622794, 0.31622724, -1.26491106]
except for the last element, y is about x plus a constant.

Now if we assume these features (except for last, y_i = x_i + c; y_last = -x_last) hold for solutions, what do they imply together with the general problem requirements?

The general problem requirements say x.x=1, y.y=1, sum(x)=0, sum(y)=0, x.y=0.

Since sum(x)=sum(y)=0, the changes to last and other elements from x to y must also sum to 0.
c*(n-1) - 2*x_last = 0. So c = x_last * 2/(n-1). (In the example case, 0.316 = 0.632 * 2/4).

sum(x)=0 implies x.[c,c,c,c,c]=0. Thus x.(x+c)=x.x=1. y=x+c except for last element, and x.y must be 0. Thus changing the last element from x_last+c=x_last*(n+1)/(n-1) to -x_last must change the dot product from 1 to 0. Thus x_last*x_last*(n+1)/(n-1) = x_last*(-x_last)+1, and x_last = sqrt((n-1)/(2n)). (In the example, 0.632 = sqrt(4/10)).

So this limits the values of n for which such rational solutions can exist to those for which (n-1)/(2n) is a square. Up to a million such values are 1, 2, 9, 50, 289, 1682, 9801, 57122, 332929.

It turns out that these are actually sufficient requirements to make a solution optimal. ANY x which fulfills sum(x)=0, x.x=1, x_last=sqrt(n-1)/(2n)) gives a solution by setting y=x+c except y_last.

To find an optimal solution of say length 50, it's now enough to find a vector of length 50 which fulfills these conditions:

sum(x)=0
x_last = sqrt(49/100) = 7/10
x.x = 1

(7/10)^2 = 49/100, so we need to fill the remaining elements of x with values that have these properties: they sum to -7/10, and their squares sum to 51/100. We'll just take -7/10, which leaves sum 0 and square-sum 2/100, and then add -1/10 and 1/10 which doesn't alter sum and fills square sum. (The published solution from Anders Kaseorg is one special case of constructing some values that have the required sum and sum of squares, but there are lots of other possibilities.)

So now we have
x=[-7/10, -1/10, 1/10, 0, 0, ..., 7/10]

and y=x+c, where c=x_last * 2/(n-1)=7/245, except last element.

y = [-7/10+7/245, -1/10+7/245, 1/10+7/245, 7/245, 7/245, ..., -7/10]

You can verify that these give a rational solution of length 50, which is valid (x.x=y.y=1, sum(x)=sum(y)=0, x.y=0), and fulfills the optimality condition f(x,y)=4.
uau is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
2022 project goals gd_barnes Conjectures 'R Us 9 2022-12-01 08:08
February 2022 tgan Puzzles 21 2022-03-23 21:59
March 2022 Xyzzy Puzzles 7 2022-03-21 10:45
January 2022 Xyzzy Puzzles 25 2022-02-14 01:08

All times are UTC. The time now is 08:25.


Sun Dec 4 08:25:55 UTC 2022 up 108 days, 5:54, 0 users, load averages: 0.66, 0.85, 0.92

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔