April 2022 - Challenge
Minimizing a sum for two orthogonal vectors
This month’s puzzle is based on a suggestion by Marco Bellocchi. Thanks, Marco!
Let x,y\in\mathbb{R}^n be two vectors, and define the function
f(x,y) = \sum_{i=1}^n\sum_{j=1}^n(|x_i-x_j|-|y_i-y_j|)^2
We wish to minimize f, subject to the following constraints on x,y: The vectors need to be orthogonal to each other and to the vector (1,1,\ldots,1) and of norm 1, i.e.,
1. \sum_{i=1}^nx_i^2=\sum_{i=1}^ny_i^2=1
2. \sum_{i=1}^nx_i=\sum_{i=1}^ny_i=0
3. \sum_{i=1}^nx_iy_i=0
The lower bound for f appears to be 4, but we know of no proof for general n. Nevertheless, we refer to a pair x,y giving f(x,y)=4 as being an "optimal solution".
For example, suppose n=5 and
x = [-0.3562014 , 0.63245526, -0.3688259 , -0.36163773, 0.45420977]
y = [-0.03997346, -0.6324558 , -0.05259805, -0.04540969, 0.77043701]
Then x,y are very close to being an optimal solution, up to a small error of at most 0.0000001
Your goal For n=20, find a pair of x,y that are 0.0000001-close to being an optimal solution. Give your solution in the exact format given above.
A bonus "*" will be given for finding an **exact** solution (f(x,y)=4) where x,y are both rational vectors (x,y\in\mathbb{Q}^n), for some n at least 5. Give your solution in a format similar to that above, but with numbers written as "a/b", e.g.,
x = [1/2, 1/3, 1/6]
A bonus "**" will be given for finding an exact rational solution for any n\ge 40, or for proving 4 is indeed the minimum value of f. (We do not know of such a solution or such a proof.)
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
29/03/2022 @ 14:00 PM EST
Solution:
04/05/2022 @ 12:00 PM EST
List Updated:
11/05/2022 @ 13:45 PM EST
People who answered correctly:
**Bert Dobbelaere (30/3/2022 9:34 PM IDT)
**Anders Kaseorg (31/3/2022 1:29 AM IDT)
Richard Gosiorovsky (31/3/2022 5:19 PM IDT)
**Bertram Felgenhauer (1/4/2022 7:43 AM IDT)
Kerry Soileau (1/4/2022 3:47 PM IDT)
Graham Hemsley (1/4/2022 5:47 PM IDT)
Joerg Schepers (1/4/2022 8:43 PM IDT)
**Phil Proudman (2/4/2022 9:03 PM IDT)
**Laurent Lessard (3/4/2022 7:58 AM IDT)
Daniel Chong Jyh Tar (3/4/2022 1:44 PM IDT)
Balakrishnan V (4/4/2022 2:27 AM IDT)
**Uoti Urpala (4/4/2022 2:55 AM IDT)
Gary M. Gerken (4/4/2022 3:28 AM IDT)
Sachal Mahajan (4/4/2022 6:20 AM IDT)
Lorenz Reichel (5/4/2022 2:56 PM IDT)
**Alper Halbutogullari &Ali Ekber Gurel (6/4/2022 9:38 AM IDT)
*Evert van Dijken (6/4/2022 12:04 PM IDT)
Paul Revenant (7/4/2022 5:10 PM IDT)
Stephen Barr (12/4/2022 7:15 AM IDT)
Fabio Michele Negroni (13/4/2022 1:15 PM IDT)
**David Greer (14/4/2022 2:32 PM IDT)
**Vladimir Volevich (14/4/2022 8:10 PM IDT)
**Nyles Heise (15/4/2022 8:58 AM IDT)
Clive Tong (16/4/2022 11:14 AM IDT)
Harald Bögeholz (17/4/2022 5:25 AM IDT)
Tamir Ganor & Shouky Dan (17/4/2022 5:15 PM IDT)
John Goh (18/4/2022 5:13 AM IDT)
**Oleg Vlasii (19/4/2022 6:32 PM IDT)
Dan Dima (21/4/2022 8:12 PM IDT)
*Reda Kebbaj (23/4/2022 2:07 AM IDT)
Sri Mallikarjun J (23/4/2022 10:08 AM IDT)
**Latchezar Christov (23/4/2022 2:05 PM IDT)
**Aaron Kim (23/4/2022 4:55 PM IDT)
**Elliot Hong (23/4/2022 5:54 PM IDT)
**Grace Park (24/4/2022 4:53 PM IDT)
Teawoo Kim (24/4/2022 5:58 PM IDT)
Nir Lavee & Omer Shechter (24/4/2022 6:23 PM IDT)
**Joon Park (25/4/2022 5:38 AM IDT)
**Keun Hyong Kwak (25/4/2022 7:23 AM IDT)
Andreas Knüpfer (25/4/2022 6:32 PM IDT)
Kang Jin Cho (25/4/2022 8:13 PM IDT)
**Austin Lee (25/4/2022 9:17 PM IDT)
Chris Shannon (26/4/2022 8:26 PM IDT)
Sebastian Bohm & Martí Bosch (27/4/2022 11:43 PM IDT)
Daniel Bitin (29/4/2022 12:57 PM IDT)
**Motty Porat (30/4/2022 12:40 AM IDT)
Rob Pratt (30/4/2022 1:03 AM IDT)
Alexander Gramolin (30/4/2022 7:36 AM IDT)
Albert Stadler (30/4/2022 10:42 AM IDT)
Tim Walters (1/5/2022 1:08 AMIDT)
**Radu-Alexandru Todor (1/5/2022 3:03 AM IDT)
Amos Guler (2/5/2022 8:54 PM IDT)
**Li Li (3/5/2022 7:10 AM IDT)