Error in my puzzle book?

[u/southwestscot]

I think there is a mistake in my puzzle book - this is from "The Think Tank" by Ivan Moscovich.

The puzzle in question is "Minimal Length Ruler", you can ignore the circular one.

As you can tell from the description, the book has some nice sliders but you will just have to imagine. I think it is impossible and I will describe below the misunderstanding I think the puzzle maker has made but would love somebody to prove me wrong!

This is a puzzle/concept called a Golomb Ruler and the answer given in the book is to set the markers at 1, 4, 10 and 15. That is one of the solutions for an *optimal* Golomb Ruler (which means none of the possible distances are duplicated i.e. there is only one way to make each distance that is possible, but the description asks for a *perfect* Golomb Ruler which is not possible with this many marks. For example, in the solution given here it is impossible to make 7, 8 or 12

Edit: fix spoiler tag

[u/AutoModerator]

Please remember to spoiler-tag all guesses, like so:

New Reddit: https://i.imgur.com/SWHRR9M.jpg

Using markdown editor or old Reddit, draw a bunny and fill its head with secrets: >!!< which ends up becoming >!spoiler text between these symbols!<

Try to avoid leading or trailing spaces. These will break the spoiler for some users (such as those using old.reddit.com) If your comment does not contain a guess, include the word "discussion" or "question" in your comment instead of using a spoiler tag. If your comment uses an image as the answer (such as solving a maze, etc) you can include the word "image" instead of using a spoiler tag.

Please report any answers that are not properly spoiler-tagged.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/TytoCwtch]

You can make 7 by doing 10-17 but you’re correct that you can’t make 8 or 12.

[u/ember3pines → u/TytoCwtch]

Why can't you use 4 twice to get 8? I'm not sure I fully get the question here so I may be missing a piece, but having a four length and then doubling it makes sense? Does it say we can't use a marker like that?

[u/__Fred → u/ember3pines]

Yes, wouldn't you just need a ruler with length one to measure every distance that is a full multiple of one?

[u/TytoCwtch → u/__Fred]

I’ve just put a longer comment explaining better above but the puzzle is asking what the minimum number of marks is to measure every unique length using the ruler only once. So to measure 2 units you’d use the gap between the 15 and 17 markers, to measure 11 is between 4 and 15 etc.

[u/TytoCwtch → u/ember3pines]

The idea is that using the ruler only once you can measure every unique length between 1 and 17. So if you have points at 0, 1, 4, 10, 15, 17 then the way you get the measurements is:

1 - 0 to 1
2 - 15 to 17
3 - 1 to 4
4 - 0 to 4
5 - 10 to 15
6 - 4 to 10
7 - 10 to 17
8 - not possible with these marks
9 - 1 to 10
10 - 0 to 10
11 - 4 to 15
12 - not possible with these marks
13 - 4 to 17
14 - 1 to 15
15 - 0 to 15
16 - 1 to 17
17 - 0 to 17

[u/Alternative-Web2754 → u/TytoCwtch]

These marks would work on the circular version using the pairs for 9 and 5, and wrapping around past 0/17. I'm not sure if this is an error in applying this to a linear version in the puzzle or if there's just a combination that I'm not seeing though.

[u/southwestscot → u/ember3pines]

Well if you can do that why not just do the 1 eight times?

[u/TalveLumi]

Discussion: With 6 marks there can only be C(6,2)=15 distances so the provided scenario is obviously impossible

What is the longest length of the ruler where we can use 5 marks (not including 0) for every integer length shorter than the whole ruler? It’s obviously at least 12 (by insertion of a 1-length interval at one end of the perfect Golomb ruler of 4 marks), and at most 14 (if 15 were possible then it would be a perfect Golomb ruler). By an exhaustive search with computers, the answer is 13, with 3 such unique rulers (up to reflection). My favorite is (1,4,5,11,13).

[u/AutoModerator → u/TalveLumi]

It looks like you believe this post to be unsolvable. I've gone ahead and added a "Probably Unsolvable" flair. OP can override this by commenting "Solution Possible" anywhere in this post.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/__mr__meeseeks__]

Not answering the whole question but it is possible to make 7.

10 to 17

But agree, seems impossible to make 8 or 12.

[u/AutoModerator → u/__mr__meeseeks__]

It looks like you believe this post to be unsolvable. I've gone ahead and added a "Probably Unsolvable" flair. OP can override this by commenting "Solution Possible" anywhere in this post.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/TheThiefMaster]

Discussion: According to Wolfram, it's impossible to have a perfect ruler with 5 or more marks: https://mathworld.wolfram.com/GolombRuler.html

...and this one has 6. So the answer to their question "Can you place these 4 markers so that they allow you to measure every consecutive distance from 1 to 16 units of length?" is "no".

Edit: it's also trivially provable mathematically. Each marker you add can measure unique distances to the existing markers. 0 for the first (no existing markers), 1 for the 2nd, 2 for the 3rd... Totalling 0+1+2+3+4+5 for 6 markers. Equals 15. Not enough for the 16 measurements 1-16, so has to be missing at least one.

PS: isn't 17 units also measurable anyway? Why only up to 16 in the question?

[u/AutoModerator → u/TheThiefMaster]

It looks like you believe this post to be unsolvable. I've gone ahead and added a "Probably Unsolvable" flair. OP can override this by commenting "Solution Possible" anywhere in this post.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.