October 2018

Xyzzy · 2018-10-02, 13:28

http://www.research.ibm.com/haifa/po...tober2018.html

a1call · 2018-10-03, 03:16

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.

axn · 2018-10-03, 04:10

Quote:

Originally Posted by a1call

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.

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.

a1call · 2018-10-03, 05:00

Quote:

Originally Posted by axn

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.

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.

axn · 2018-10-03, 06:28

Quote:

Originally Posted by a1call

some sort of an ingenious shortcut of some sort

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

KangJ · 2018-10-03, 16:24

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...

a1call · 2018-10-03, 17:06

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.

science_man_88 · 2018-10-03, 18:58

Quote:

Originally Posted by KangJ

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...

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.

KangJ · 2018-10-04, 07:08

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)

a1call · 2018-10-05, 04:38

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.

The best I have found was for a 39x36 = 1404 matrix, which I failed to reduce without duplicating areas.

bsquared · 2018-10-05, 16:49

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.

2018-10-02, 13:28	#1
Xyzzy "Mike" Aug 2002 2⁵·257 Posts	October 2018 http://www.research.ibm.com/haifa/po...tober2018.html

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
October 2017	Xyzzy	Puzzles	9	2017-11-07 15:18
October 2016	R. Gerbicz	Puzzles	10	2016-11-01 13:35
October 2015	LaurV	Puzzles	3	2015-11-02 15:22
October 2014	Xyzzy	Puzzles	8	2014-11-02 19:03
13 October is approaching!	Joe O	Prime Sierpinski Project	1	2010-10-09 06:12

2018-10-03, 03:16	#2
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 3×5×137 Posts	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.

2018-10-03, 16:24	#6
KangJ Jul 2015 9₁₀ Posts	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...

2018-10-03, 17:06	#7
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 3·5·137 Posts	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.

2018-10-04, 07:08	#9
KangJ Jul 2015 3² Posts	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 (11) 4 points: (0,0) (0,1) (1,2) (2,0) with area 4 (22) 5 points: (0,0) (0,1) (2,3) (4,2) (5,0) with area 15 (53) 6 points: (0,0) (0,1) (1,4) (3,5) (4,0) (6,2) with area 30 (65) 7 points: (0,0) (1,0) (2,4) (5,6) (10,5) (11,1) (11,3) with area 66 (116) 8 points: (0,1) (0,3) (1,6) (4,6) (7,7) (12,0) (14,8) (15,2) with area 120 (158)

2018-10-05, 04:38	#10
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 2055₁₀ Posts	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. The best I have found was for a 39x36 = 1404 matrix, which I failed to reduce without duplicating areas.

2018-10-05, 16:49	#11
bsquared "Ben" Feb 2007 3×1,171 Posts	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.