mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2018-10-02, 13:28   #1
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

22·2,087 Posts
Default October 2018

http://www.research.ibm.com/haifa/po...tober2018.html
Xyzzy is offline   Reply With Quote
Old 2018-10-03, 03:16   #2
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

22×3×181 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2018-10-03, 04:10   #3
axn
 
axn's Avatar
 
Jun 2003

5,179 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
axn is offline   Reply With Quote
Old 2018-10-03, 05:00   #4
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

22·3·181 Posts
Default

Quote:
Originally Posted by axn View Post
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.
a1call is offline   Reply With Quote
Old 2018-10-03, 06:28   #5
axn
 
axn's Avatar
 
Jun 2003

10100001110112 Posts
Default

Quote:
Originally Posted by a1call View Post
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?
axn is offline   Reply With Quote
Old 2018-10-03, 16:24   #6
KangJ
 
Jul 2015

10012 Posts
Default

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...
KangJ is offline   Reply With Quote
Old 2018-10-03, 17:06   #7
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

217210 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2018-10-03, 18:58   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by KangJ View Post
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.
science_man_88 is offline   Reply With Quote
Old 2018-10-04, 07:08   #9
KangJ
 
Jul 2015

32 Posts
Default

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)
KangJ is offline   Reply With Quote
Old 2018-10-05, 04:38   #10
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

22·3·181 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2018-10-05, 16:49   #11
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3·1,193 Posts
Default

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.
bsquared is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 21:54.


Mon Nov 29 21:54:28 UTC 2021 up 129 days, 16:23, 0 users, load averages: 1.45, 1.52, 1.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.