October 2018
 

[url]http://www.research.ibm.com/haifa/ponderthis/challenges/October2018.html[/url]

I wonder if there has ever been a challenge that has gone unsolved for an entire month.
Or at least a couple of weeks.
No solvers listed on 2nd day of the month.
The challenge has been listed for 6 days so far.:smile:

[QUOTE=a1call;497261]I wonder if there has ever been a challenge that has gone unsolved for an entire month.
Or at least a couple of weeks.
No solvers listed on 2nd day of the month.
The challenge has been listed for 6 days so far.:smile:[/QUOTE]

Not listed does not mean no solvers at all. When they get around to updating the page, we'll see the actual dates. Almost sure someone would've solved it within hours.

[QUOTE=axn;497268]Not listed does not mean no solvers at all. When they get around to updating the page, we'll see the actual dates. Almost sure someone would've solved it within hours.[/QUOTE]
If so would take a lot of paralleling for this month or some sort of an ingenious shortcut of some sort. A lot of possible triangles to brute force through which should none equate.
Anyhow it's quite rare for no solvers to be listed on the 1st day of the month.

[QUOTE=a1call;497270]some sort of an ingenious shortcut of some sort[/QUOTE]

Isn't that the essence of problem solving - finding an insight that leads to an efficient solution?

I think that using Brute-force method is not intended at all because the search space is too large even if an efficient algorithm is applied to remove the overlapped cases.

However, I still have not figured out any approaches or ideas to reach the solution.

There should be 165 different areas of triangles.

Any of three points cannot be on the same line.

Any of two segments cannot be parallel.

Is there any other constraints?

Maybe dividing the space (with grid of dimension 600) into small rectangular pieces with a point inside can be a good approach.

...needs more pondering...

I don't think being parallel is relevant. What is, is that no 3 points should be on a straight line.
None of the constraints are much of challenge other than having 165 triangles (formed by 11 vertexes) which none have the same area. Plenty of triangles will end up with equal areas even with differing side lengths.
I think that perhaps a manual arrangement is the path of least resistance.

[QUOTE=KangJ;497302]I think that using Brute-force method is not intended at all because the search space is too large even if an efficient algorithm is applied to remove the overlapped cases.

However, I still have not figured out any approaches or ideas to reach the solution.


There should be 165 different areas of triangles.

Any of three points cannot be on the same line.

Any of two segments cannot be parallel.

Is there any other constraints?

Maybe dividing the space (with grid of dimension 600) into small rectangular pieces with a point inside can be a good approach.

...needs more pondering...[/QUOTE]

Cutting out reflections and rotations cuts the space by between 4 and 8 fold. Cutting out grids that are too small, will also help. As will cutting out translations. Scalings can help in cases of equal area. etc.

I tried to figure out more simple cases with smaller numbers of points.

The results are shown below with minimum area.

Any ideas or intuitions can be derived from the simple cases?

3 points: (0,0) (0,1) (1,0) with area 1 (1*1)
4 points: (0,0) (0,1) (1,2) (2,0) with area 4 (2*2)
5 points: (0,0) (0,1) (2,3) (4,2) (5,0) with area 15 (5*3)
6 points: (0,0) (0,1) (1,4) (3,5) (4,0) (6,2) with area 30 (6*5)
7 points: (0,0) (1,0) (2,4) (5,6) (10,5) (11,1) (11,3) with area 66 (11*6)
8 points: (0,1) (0,3) (1,6) (4,6) (7,7) (12,0) (14,8) (15,2) with area 120 (15*8)

I have been on the subject for a few days now. I don't see any feasible approach other than dedicating 10s of cores to the job.:smile:
The best I have found was for a 39x36 = 1404 matrix, which I failed to reduce without duplicating areas.

Still no correct answers listed on the page...

I've written a solver that finds a solution to N=10 (on the max-sized grid) in a couple minutes, but the best it's done so far on N=11 is a 161-triangle solution (4 duplicates). I should probably take that one and try to tweak it by hand.