20150531, 21:36  #1 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
5×23×79 Posts 
June 2015
Ponder This, June 2015
I have discovered a truly marvelous demonstration of this proposition that this margin is too narrow to contain. ...Too soon? ;) Last fiddled with by Batalov on 20150602 at 15:50 Reason: 1st of June comes earlier in Beer Sheva but not as early as in Lamphun 
20150531, 21:45  #2  
"Kieren"
Jul 2011
In My Own Galaxy!
26D0_{16} Posts 
Quote:


20150601, 23:12  #3 
Jan 2015
253_{10} Posts 

20150602, 15:00  #4 
"Robert Gerbicz"
Oct 2005
Hungary
10101100011_{2} Posts 
The problem is out! Not sure why ibm is using lots of different (semi)working addresses, what is the fun with using multiple links for the same site? Anyway, here is the problem: https://www.research.ibm.com/haifa/p.../June2015.html
(not sure how long it is online), on the other link: http://domino.research.ibm.com/Comm/...s/May2015.html you can't even see a clickable link for the June's problem. Last fiddled with by R. Gerbicz on 20150602 at 15:01 
20150615, 22:10  #5 
"Robert Gerbicz"
Oct 2005
Hungary
7·197 Posts 
There was an update:
"Update (14/6): We'll add a star to the best solver. Currently it is Alex Wagner with a convex hull of 7,719,775." 
20150620, 06:41  #6 
Romulan Interpreter
Jun 2011
Thailand
5×11×157 Posts 
Now, this is a very interesting problem, and LaurV has nothing to do this weekend...
Is it only me, or the problem is very suitable for a “genetic” approach? I “feel” it can be solved mathematically (i.e. an equation can be obtained for the spiral that pass through those 9 points, and resolved for a “maximum possible area”) but a genetic approach is much nicer. So, we have a chromosome which has a “head” formed by the 2 given starting points (4 integer coordinates), it has a “body” containing the other 7 points (14 integers), and a “tail” where we do the calculus (few more integers to retain the partial norms/distances, coordinates of center points at each step, and, at the end of the tip of the tail, the “area” we are interested in. [well, memory can be saved by not storing the head at all, but this is behind the point of the discussion] One could remark that we don’t need a complicated algorithm to calculate the convex hull, if we always arrange the points in a spiral (no, I don’t have a proof that the area is maximized in this way, it is just “common sense”), then the “convex hull” is in fact the area given by the last 4 points. Yes, because this is what the “intermediary” points do: they “prepare the sling” to shot those 4 points as far away as possible. Shooting stars… or shooting the moon? So, a chromosome (head, body, tail) will divide itself in other (maximum 56) chromosomes, in the next generation, where at least one of the coordinates in the body varies with +1 or 1 (the head is not changed, and the tail is only calculus depending on the head and body). Of course, we can have +n or n, for a small n, (and maximum n*56 offsprings in next generation) but this is not really important. After G generations we have (say) about ~50^G chromosomes (many of them “fall back” into their parents, at the third, forth, etc generation, same coordinates which once increased, can now decrease, but well, this is how the “evolution” works… ). So, we have to “trim” them. For each “child” which we spawn, we calculate the “tail” and we "cut the head of those with blue tail, because we only like green tail"… ok, this sounds more like snaketheory, orange head green tail is good, orange head blue tail is not good (remember, the tip of the tail contains the area). So, we arrange the snakes descending, by the color of the tail, keep few millions of the good snakes, trim the bad snakes, rewind the tape, breed a new generation. From time to time we examine the snakes on the head of the list, to see if we got that one with pureemeraldgreen tail... Still I can't understand why the people who sent answers stopped at 7 millions, because I reached answers into 16M already, and still feel comfortable. You can see here how the first chromosome in the list looks from a generation to the other. The 9 blue dots are the points (I draw the line just to see the order), and the 8 red dots are the centers of the averaged former points. Technically, the distance from a blue point to its corespondent red point must not be more than 3 times the previous point's distance (well, this is heavier to explain than to do!). At the end of the video there are 3 or 4 configurations (snakes) which reach an area over 15M, one close to 17M (there is no comment, but if you watch the coordinates, you will see when they jump from hundreds to thousands). I have to check if I didn't do a stupid mistake in computing those tails, then I will send my answer in. Last fiddled with by LaurV on 20150620 at 06:58 Reason: WTF is with strange formatting? (I copy/pasted some text, is that why?) 
20150620, 07:47  #7  
"Robert Gerbicz"
Oct 2005
Hungary
7×197 Posts 
Quote:
"Technically, the distance from a blue point to its corespondent red point must not be more than 3 times the previous point's distance" You need (from ponder this): "Make sure that every measurement is not exceeding 3 standard deviations from the mean of all the previous one." Lookup at https://en.wikipedia.org/?title=Standard_deviation . 

20150620, 14:12  #8 
Romulan Interpreter
Jun 2011
Thailand
5·11·157 Posts 
If you look to my video you can see that the "standard deviation" is used, even if I call it "distance". When you compute the standard deviation in the complex plane, it is the square root of the sum of the squares of the distances. Which is (from Pythagoras' Theorem) the sum of the squares of the differences of coordinates (grr, it sounds more complicate to explain than to do, again!). Give or take some distributivity rules, this is just a "distance" for me, but be sure the right formulas were used there. The first center is in (0,0) and the first 3SD is 300, so the third point can be anywhere in a circle with a radius of 300, centered in (0,0). Then, depending on this third point, you find the second center, the second circle can have a radius of up to ~500 (the second 3SD), centered in this new center, and the forth point has to be anywhere inside of this second circle. Etc.
However, you are right about the limit value, it is around 7M7 for me too. I found that shortly after I posted. Due to a stupid programmer error, i was doing the "floor" function (to restrict the calculus to gaussian integers) and totally forgot that for negative numbers, this is the integer which is higher in absolute value. You must do "floor(x)" for positives, and "floor(x)" for negatives, to round toward zero Amazing how such small error propagates, the first 3SD is 300, the second goes to 485 or so, but if you put the first only to 300.66, then you can find the next point to get a value for the 3SD over 500, Last fiddled with by LaurV on 20150620 at 14:20 
20150625, 09:02  #9 
Romulan Interpreter
Jun 2011
Thailand
5×11×157 Posts 
Ok, I did a very beautiful implementation for my genetic algorithms, with few tricks and optimizations, and with the right rounding to integers (i.e. when modify a point, it is possible that the other points coming after it will get "out of range", so I did a nice trick to avoid this, of which I am very proud). I love how it works. I let it run for a day (a bit more than 13 hours) in one core. The largest score it produced is 7M64. That is far behind the best displayed score
We are still struggling (but refusing stubbornly to write a "full space search", which would be kinda slower, even with some heuristic like moving the points only on the circles' perimeter, and not inside of all the disks). 
20150702, 13:22  #10 
"Mike"
Aug 2002
23×331 Posts 

20150707, 14:59  #11 
"Robert Gerbicz"
Oct 2005
Hungary
7·197 Posts 
My sent solution was (not posting the actual code and I have made no big attack to find much better point set).:
One solution: (100,0),(100,0),(80,289),(443,235),(286,608),(1000,196),(86,1604),(527,2045),(3120,422) with convex hull's area=7706357, see my attached code that has found this ( random algorithm and depends on the initial seed, that is time(NULL), so it is unlikely that it will rediscover the same polygon for a new run, but finds several good point sets, with area>=7700000 ). First I have found a good solution (convex hull's area is close to 7700000), then optimized the point set by perturbation. To find a good solution I have generated some random point sets where in that each point is (very) far from the previous point's average (but still closer than 3*standard dev.), if we choose (u,v) in such a way that u=x+r*cos(deg) v=y+r*sin(deg) where r<=3*sd (here sd is the standard dev.) and (x,y) is the average of the points so far, then the distance of (u,v) from (x,y) is r, round this (u,v) to an integer point (we still need to check that we won't be far from (x,y)). Finally find the convex hull of the polygon with Jarvis march, then the calculation of the polygon's area is easy. (the double of the area is an integer). One such convex hull had area=7680036.5 . To perturbate this point set I have choosen close degrees to the above original degree selection. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
June 2017  R. Gerbicz  Puzzles  14  20170703 20:01 
June 2016  Xyzzy  Puzzles  16  20160707 02:51 
LLRnet/PRPnet rally June 4th6th  gd_barnes  No Prime Left Behind  61  20100730 17:28 
Max on the move: vacation June 28/30July 4  mdettweiler  No Prime Left Behind  8  20090705 05:20 
LLRnet server rally 400<k<1001 June 2022  mdettweiler  No Prime Left Behind  67  20080623 15:32 