19
$\begingroup$

Suppose you're given six stakes and an unlimited length of string. Your objective is to plant the stakes in a flat patch of ground in such a way that you can wrap the string around the stakes in different ways to create simple polygons with integral (i.e. integer-valued) areas (see Fig. 2).

There are some restrictions:

  1. This is a 2D problem.
  2. No three stakes (or more) may be colinear. A line drawn through any two stakes must not pass through any other stakes (see Fig. 3).
  3. Areas must be circumscribed exactly.
  4. The stakes are ideal vertices (having zero cross-sectional area), and the string may only create perfectly straight, ideal edges between the stakes.
  5. The string must visit each stake once and only once, and terminate where it begins (thus forming a closed polygon).
  6. Stake coordinates should be expressed in meters (m). The stakes can be positioned at any real coordinates so long as all stake coordinates are unique.
  7. All six stakes must be used.

There are two separate puzzle objectives:

  1. The accepted answer will go to the first (correct) answer that gives grid coordinates that can produce at least 6 consecutive integral areas ≤ 20 m2. (For example, areas of 3,4,5,6,7, and 8 m2, respectively). The answer should also specify the winding order of the string (around the stakes) for each polygon.

    For example, an answer might look like

    Stake 1: (5 m,2 m), Stake 2: (3 m,4 m), ...

    Area 3 m2: 1 → 2 → 5 → 3 → 4 → 6 → 1
    Area 4 m2: 1 → 3 → 4 → 6 → 2 → 5 → 1
    ...

    It is acceptable if the stakes can produce additional polygons with areas not comprising the 6 consecutive integers in the solution.

  2. A bounty of 100 rep will go to the (correct) answer that gives the grid coordinates and winding rules that can produce the greatest number of consecutive integral areas ≤ 20 m2.

    In the event of a tie, the earliest solution will receive the bounty.

Good luck staking your claim. ;)

Special thanks to McMagister for pointing out Pick's theorem as a simple way to compute the area of polygons with integer coordinates.


Examples of Legal and Illegal Polygons

                 legal and illegal polygons in "Staking Out the Integers"


                               valid stake placement and several windings
                                                                            Fig. 2


                                         invalid stake placement due to colinearity
                                                                            Fig. 3

$\endgroup$
  • 5
    $\begingroup$ Pick's theorem will be helpful here. $\endgroup$ – McMagister Dec 9 '14 at 12:26
  • $\begingroup$ @McMagister +1 and thanks. But I think point 6) in the riddle allows for a bit more flexibility than that, doesn't it? (Well, one can break down into smaller units than square-meters, I suppose...) $\endgroup$ – BmyGuest Dec 9 '14 at 16:33
  • 1
    $\begingroup$ @BmyGuest: I've added some new figures (with references) to clarify the meaning of a few concepts. I prefer to keep the figures at the end simply as a matter of layout. You're also correct to assert that the stakes don't need to be placed at integer coordinates. I will point out, however, that using integer coordinates is probably the easiest way of guaranteeing areas will be multiples of $\frac{1}{2}$, and that all of the solutions I've found have integer coordinates. $\endgroup$ – COTO Dec 9 '14 at 18:22
  • 1
    $\begingroup$ Cool puzzle. Wish I had time to work on it right now. Next step is to post this as a Code Golf challenge and see what absurdities those people come up with! $\endgroup$ – Josh Caswell Dec 9 '14 at 19:37
  • 1
    $\begingroup$ One of my favourite puzzles on site so far! Where did you get the idea for this one? $\endgroup$ – BmyGuest Dec 10 '14 at 7:24
9
+100
$\begingroup$

I'm sure there's a lot of solutions for $\geq 6$ because it didn't take me long to find one:

[(2, 2), (4, 5), (2, 8), (8, 4), (7, 2), (6, 4)] 12
[(2, 2), (6, 4), (7, 2), (8, 4), (4, 5), (2, 8)] 13
[(2, 2), (2, 8), (8, 4), (7, 2), (6, 4), (4, 5)] 14
[(2, 2), (4, 5), (2, 8), (8, 4), (6, 4), (7, 2)] 15
[(2, 2), (2, 8), (4, 5), (8, 4), (6, 4), (7, 2)] 16
[(2, 2), (2, 8), (4, 5), (6, 4), (8, 4), (7, 2)] 17

Finding the most consecutive, on the other hand, is going to be a bit harder.

Diagrams:

enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here


Here's a solution with 12 consecutive:

9  ((5, 4), (3, 0), (6, 4), (9, 2), (6, 10), (7, 6))
10 ((5, 4), (6, 10), (9, 2), (7, 6), (6, 4), (3, 0))
11 ((5, 4), (6, 10), (3, 0), (6, 4), (9, 2), (7, 6))
12 ((5, 4), (6, 10), (7, 6), (9, 2), (6, 4), (3, 0))
13 ((5, 4), (6, 10), (9, 2), (6, 4), (7, 6), (3, 0))
14 ((5, 4), (3, 0), (6, 10), (7, 6), (9, 2), (6, 4))
15 ((5, 4), (3, 0), (6, 10), (9, 2), (6, 4), (7, 6))
16 ((5, 4), (6, 10), (3, 0), (9, 2), (6, 4), (7, 6))
17 ((5, 4), (6, 10), (7, 6), (6, 4), (9, 2), (3, 0))
18 ((5, 4), (6, 10), (6, 4), (7, 6), (9, 2), (3, 0))
19 ((5, 4), (6, 10), (3, 0), (9, 2), (7, 6), (6, 4))
20 ((5, 4), (6, 10), (9, 2), (3, 0), (6, 4), (7, 6))
$\endgroup$
  • $\begingroup$ My best "most consecutive" is 10. ;) $\endgroup$ – COTO Dec 9 '14 at 21:34
  • $\begingroup$ @COTO Do you have some sort of verification method? I think I have 12 $\endgroup$ – Sp3000 Dec 9 '14 at 22:08
  • 1
    $\begingroup$ I do. It's a function written in MATLAB. I've posted it to pastebin. You can validate your stakes using As = stakeareas( [5, 4; 3, 0; 6, 4; 9, 2; 6, 10; 7, 6] ), which returns As = 9 10 11 12 13 14 15 16 17 18 19 20 on my machine. Good job! ;) $\endgroup$ – COTO Dec 10 '14 at 13:19
0
$\begingroup$

Incorrect answer, as I misunderstood the question. (See comments). I'll leave it for reference while thinking of a proper solution.


What have I missed?

I've read the instructions again and again, but I don't get it.

I am free to place the stakes at any real (unique) coordinate?

6. Stake coordinates should be expressed in meters (m). 
   The stakes can be positioned at any real coordinates so long as all 
   stake coordinates are unique.

Well, then I can simply do something like:

Any arbitrary circular shape like this hexagon:
Hex

Can't I?

But in this case, I'm absolutely free to extend shrink the 3 parameters a,b,c to any floating point value to give me an area I like, and the stake coordinates will be:
(0|0) -> (a|-b) -> (2a|0) -> (0|c) -> (a|c+b) -> (2a|c)

I can then make for example:
A = 1 ==> a=0.5 b=c=0.5
A = 2 ==> a=1 b=c=0.5
A = 3 ==> a=1.5 b=c=0.5
....

As this clearly isn't a real puzzle, I suppose there is either some catch I haven't seen, or the puzzle text is missing something. Should it be "integer" values for the stakes? That would make more sense for me..

$\endgroup$
  • 3
    $\begingroup$ I think you're supposed to get a bunch of different areas with the SAME placement of the stakes, by choosing a different ordering of the stakes. $\endgroup$ – Julian Rosen Dec 9 '14 at 17:15
  • 1
    $\begingroup$ @JulianRosen !! Thanks. I knew I must have missed something, I just didn't see it :c) $\endgroup$ – BmyGuest Dec 9 '14 at 17:17
  • 1
    $\begingroup$ Julian is correct. There is only one placement of the stakes, and then different ways of wrapping the string around them yield different areas. Consider the three valid polygons in the example in the OP. All have the same stake coordinates, but a different winding order in each case yields different areas. $\endgroup$ – COTO Dec 9 '14 at 17:17
  • $\begingroup$ @COTO There is one more clarification I would add. Point 2. It means no 3 stakes must be on a single line, right? So it is also not allowed to have a polygon of (1)->(2)->(3)->(4)->(5)->(6)->(1) with (1) (2) & (x) on the same line, correct? It's no three stakes must be on a straight line", not: no three successive stakes must be on a straight line", correct? Maybe a "false" drawing for this case would make it nicer... $\endgroup$ – BmyGuest Dec 9 '14 at 17:21
  • $\begingroup$ @BmyGuest: You are correct. I'll add an additional example to make that clearer. $\endgroup$ – COTO Dec 9 '14 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.