July 2019

[axn]

**Nevermind**

[Kebbaj]

Originally Posted by Dieter

195=3*5*13, so the only realistic possibility is 13*15

It‘s no problem to find shapes with area 13 respectively 15.
Or I have misunderstood your problem...

15 * 13.
4 possibilité de figure geometrique possible, n'est ce pas?

[Kebbaj]

Originally Posted by Dieter

195=3*5*13, so the only realistic possibility is 13*15

It‘s no problem to find shapes with area 13 respectively 15.
Or I have misunderstood your problem...

15 * 13
.4 possibility of polygon shapes, is not it?

[Dieter]

Originally Posted by Kebbaj

15 * 13.
4 possibilité de figure geometrique possible, n'est ce pas?

There is only one size mXn where I can find areas of 15.
If I permit every point as point of start I find 224 combinations a1... with area 15. But every shape appears with 112 variations: every corner can be choosen as point of start (14), we can reverse the direction of rotation (28) and we can reflect the shape horizontally (56) and vertically (112).
So I have only two different shapes with area 15.
In the same mXn my code is finding 1456 combinations with area 13. So there are 1456 : 112 = 13 different shapes.


Je crois qu'il y a 2 figures géometriques avec 15 et 13 figures avec 13.

[Dieter]

Drawing the 13 shapes shows that there are really 13 different figures with area 13;
7 from them with three points in one straight line.

[Kebbaj]

Originally Posted by Dieter

Drawing the 13 shapes shows that there are really 13 different figures with area 13;
7 from them with three points in one straight line.

13 possibility is odd ??
It seems to me that each polygone have homotethic counterpart. So the possibilities should be even for a specific area of ​​n.
As in this example of area 13.


"Are 13 can be given because it does not serve much to chalange ibm".

[axn]

Originally Posted by Kebbaj

It seems to me that each polygone have homotethic counterpart.

Therefore they are counted as one unique figure.

[Dieter]

Originally Posted by axn

Therefore they are counted as one unique figure.

That‘s right. Otherwise the number had to be divisible by 4, because the shapes can be reflected on the horizontal, too.
The pictured shapes are one of 13 different shapes. One of the seven with 3 points in a line.

[Kebbaj]

Originally Posted by Dieter

That‘s right. Otherwise the number had to be divisible by 4, because the shapes can be reflected on the horizontal, too.
The pictured shapes are one of 13 different shapes. One of the seven with 3 points in a line.

You are quite right. We can also think about Horizontale.
So you mean, that there is 13 solution of the area 13, which will give 13 * 4 of mirrored solution.

Brvo. Very Nice.
My psycovisual area has only succeeded in having 2 poswibilty of area 13.
I do that only manually.

[Xyzzy]

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

[yae9911]

Originally Posted by Xyzzy

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

This is somewhat unusual here, but since I am the one who suggested the riddle and the provided solution is very laconic and incomplete, this discussion offers me the opportunity to provide some background information on the July challenge. Since some of you have handled the task and maybe even had fun with the solution, I think it's a pity that the information I sent to the puzzle editor was not made available anywhere else.

My puzzle suggestion was a by-product of some submissions related to knight's tours to the OEIS database, to which I regularly submit contributions. E.g.
https://oeis.org/A323131 https://oeis.org/A323134 https://oeis.org/A323560 https://oeis.org/A323700 https://oeis.org/A323699
Extending those sequences is not easy due to the growth of the solution space. The puzzle is related to the yet unknown next term of https://oeis.org/A323134
which also has a link to visualizations of short closed paths: http://www.randomwalk.de/sequences/a323134.htm
For the graphical representation of the paths I have used a program that was written for a completely different purpose http://www.enginemonitoring.net/azpc...czzresults.htm, but because the changes in direction at each jump are very close to multiples of 9 degrees, very good approximate representations of exact knight's tours result, but with closed paths now and then not be recognized. To see the tours in the usual orientation on a chessboard, you still have to rotate them, which is even possible in the program by choosing "Orientation".


My first proposal was about paths of length 12, but I found that almost everything was already available on the web. Therefore I sent an update. Since there is nothing personal or problematic in the proposal I sent to IBM's puzzle master, I can show it here unchanged:
...
almost everything related to record hunting for this problem is available on some webpages. See G. P. Jelliss's Non-Intersecting Paths http://www.mayhematics.com/t/2n.htm for an introduction to the topic. After a careful examination I've found that not only the solutions for quadratic boards, but also those for rectangular boards are published in great detail. What I had suggested (finding a path of length 12 on a board of area < 36) is covered by the solutions Eric Bainville found in the year 2000 ( Self-avoiding walks of a knight on a square chessboard http://euler.free.fr/knight/index2.html ), where the two 5X6 solutions are given in the list of 6X6 solutions as 2 pairs of mirror images (e.g. http://euler.free.fr/knight/closed6-027.html ).


Most of the links on J-C Meyrignac's Webpage ( Non-crossing knight tours http://euler.free.fr/knight/index.htm ) are outdated or dead and no concrete details of the solutions are provided, but there exists a well maintained webpage by Alex Chernov ( Uncrossed knight's tours. http://ukt.alex-black.ru/index.php ). For all reasonable problem sizes, links to full solutions are provided there, see e.g. http://ukt.alex-black.ru/index.php?m=6&n=5&closed=1 for the mentioned L=12 solutions on the 5X6 board.

In my opinion, going for larger problems will not make an attractive challenge, but would discourage many of the regular participants, due to complexity of methods and required computational resources. Therefore my idea would be to stay with relatively short closed non-crossing tours, but add a little twist that inhibits the use of the published solutions and forces the competitors to perform some own analysis and write programs.

My revised suggestion would be as follows: Find two closed non-crossing knight's path of 14 moves on a chessboard of area <= 40, such that one path minimizes the area of the path polygon and the other path maximizes the area of the path polygon. The path polygon is obtained by joining the visited fields by straight line segments. The line segments are sqrt(5) long, but all possible polygons have integer areas. The 3 possible paths of length 4 have path polygon areas of 3, 4, 5: a1 c2 d4 b3 a1 -> A=3, c1 e2 c3 a2 c1 -> A=4, c1 d3 b4 a2 c1 -> A=5.

Although one can look up the minimum size of the chessboard for path length 14 to be 5X7 (or 7X5) at http://ukt.alex-black.ru/index.php?m=7&n=5&closed=1 , the areas of the path polygons of the 5 solutions provided there are 10 or 11, which is not minimal.
See http://www.randomwalk.de/pthissuggest/14_A35A.htm
For the chessboard with area 36=9X4 there is only one solution http://www.randomwalk.de/pthissuggest/14_A36A.htm with polygon area 10.
For the chessboard with area 40, there are 107 paths on 8X5 or 5X8 and 7 paths on 10X4 or 4X10.
http://www.randomwalk.de/pthissuggest/14_A40A.htm gives links to all 114 solutions.
3 of the 114 paths have the minimal area 8:
d6 e8 c7 d5 b6 c4 d2 b3 a1 c2 e1 d3 c5 e4 d6

d6 e8 c7 d5 b6 c4 a5 b3 a1 c2 b4 d3 c5 e4 d6

g3 h5 f4 g2 e3 c4 a5 b3 a1 c2 b4 d3 f2 h1 g3

2 of the 114 paths have maximal area 15:
b3 c5 a4 b2 d1 e3 d5 e7 c8 a7 b5 d6 c4 d2 b3

b6 d7 c5 a6 b4 a2 c1 e2 c3 e4 d6 e8 c7 a8 b6

Whereas the solutions with minimal area are somehow looking "obvious", the two solutions with area 15 can definitely only be found with some -still reasonable- effort. None of the solutions with area larger than 15 of the path polygon fits on a chessboard of area 40. Paths with polygon areas = 16 would at least need a 6X7 chessboard, e.g. f1 g3 e4 g5 e6 d4 c6 a5 c4 a3 b1 c3 d1 e3 f1 or c5 d7 b6 c4 a5 b3 a1 c2 e1 f3 e5 f7 d6 e4 c5 ( see http://www.randomwalk.de/pthissuggest/14_AllA16.htm for all paths of length 14 with polygon area 16).

Of course it might be interesting to confirm that the next term in Don Knuth's OEIS sequence https://oeis.org/A157416 is a(11)=70 as conjectured in http://ukt.alex-black.ru/index.php?m=11&n=11&closed=1 , but such an undertaking would -at least in my understanding- by far exceed the scope of the PonderThis challenges.

Best regards
Hugo