mathematical solution to a puzzle

take everything

Hi.
Just wanted to get a mathematical solution to a puzzle i came across in this month's focus magazine.
Probably simple but still.

Basically you got two vertical lines on a ruler one line labelled 0, the other labelled 11.
(ie they are 11 units apart).
How do you draw three more vertical lines on this ruler (between these two lines above) so that the distance between any pair of lines measures one of 10 different distances in whole units.

Obviously you can do this by trial and error (but it'd be tedious), but i'm interested in solving this mathematically.
Any ideas.
Thanks.

Edited for clarity:

Original 2 lines at 0 and 11 on ruler:

0

---

>11
I

---

I

Solution is obviously:
Add 3 lines at positions 1, 4 and 9 on this ruler (so that the distances between pairs of lines are 1, 2, 3, 4, 5, 7, 8, 9 and 10).

But what is the mathematical solution for n added lines.

Edit 2:
This is the solution for a 6 unit ruler for purposes of clarity

bnt

All I can think of for a mathematical solution is some kind of 2D x-y matrix of differences between x and y, though I can't quite see how.

But I don't think it's necessary - took me about 3 minutes with pen and paper. Hint:

you have 11 possible distances and you're asked for 10: the one you can't get is 6

.

click_here!!!

Could you upload a picture of the puzzle?

take everything

bnt wrote: »

All I can think of for a mathematical solution is some kind of 2D x-y matrix of differences between x and y, though I can't quite see how.

But I don't think it's necessary - took me about 3 minutes with pen and paper. Hint:

you have 11 possible distances and you're asked for 10: the one you can't get is 6

.

This particular problem as you say is doable.
Basically i was interested in a general mathematical solution for n added lines (as n increases, it would be increasingly difficult to solve with pen and paper).

take everything

click_here!!! wrote: »

Could you upload a picture of the puzzle?

Can't find it on the Focus website but i just googled "ruler problem" and i got a thing called a "Golomb ruler".
The wiki image on that page is basically this problem but with the initial markings being 0 and 6 (instead of 0 and 11 here) and a requirement to find only 6 different integer unit distances between line pairs (as opposed to 10 here).

I thought this was a bull**** puzzle- now i'm just wondering from that wiki page whether it's more difficult than that.

click_here!!!

I think I've found a simple way of doing it.

Draw out the line. Then mark off the interval of length 1 away from the start (1).

Next mark off the interval of length 2 away from the end (9).
Now mark off the interval of length 3 away from the leftmost number you have marked. (4)
Mark off the interval of length 4 away from the rightmost number you have marked off (5).

So the numbers you have marked are: 1,4,5,9. This gives you 11 distances with 4 markings.

You now need to get rid of one of the markings, in return for getting rid of one of the distances.

List the distances, and the intervals associated with them:
1: [0,1]
2: [9,11]
3: [1,4]
4: [0,4]
5: [4,9]
6: [5,11]
7: [4,11]
8: [1,9]
9: [0,9]
10: [1,11]
11: [0,11]

By analyzing these intervals, we see that:
Marking @ 1 is used in 5 distances.
Marking @ 4 is used in 4 distances.
Marking @ 5 is used in 1 distance.
Marking @ 9 is used in 5 distances.
Therefore, if you erase the marking at 5, you get 10 distances with 3 markings.

Markings: 1,4,9.
This will mean you won't have an interval of distance 6, as a previous poster has hinted.

PS: how do you find Focus magazine? I used to get it all the time, but now the articles seem a bit simple. (The puzzles aren't though!) Also, the price is rather high compared to in the UK.

take everything

click_here!!! wrote: »

I think I've found a simple way of doing it.

Draw out the line. Then mark off the interval of length 1 away from the start (1).

Next mark off the interval of length 2 away from the end (9).
Now mark off the interval of length 3 away from the leftmost number you have marked. (4)
Mark off the interval of length 4 away from the rightmost number you have marked off (5).

So the numbers you have marked are: 1,4,5,9. This gives you 11 distances with 4 markings.

You now need to get rid of one of the markings, in return for getting rid of one of the distances.

List the distances, and the intervals associated with them:
1: [0,1]
2: [9,11]
3: [1,4]
4: [0,4]
5: [4,9]
6: [5,11]
7: [4,11]
8: [1,9]
9: [0,9]
10: [1,11]
11: [0,11]

By analyzing these intervals, we see that:
Marking @ 1 is used in 5 distances.
Marking @ 4 is used in 4 distances.
Marking @ 5 is used in 1 distance.
Marking @ 9 is used in 5 distances.
Therefore, if you erase the marking at 5, you get 10 distances with 3 markings.

Markings: 1,4,9.
This will mean you won't have an interval of distance 6, as a previous poster has hinted.

PS: how do you find Focus magazine? I used to get it all the time, but now the articles seem a bit simple. (The puzzles aren't though!) Also, the price is rather high compared to in the UK.

Thanks.
Any idea about a solution for n lines.
(not a subcriber to Focus, get it the odd time; it's kinda pop-science-ish as you say. New Scientist, SciAm, Discover etc are probably better).

bnt

Have a look at the Wolfram MathWorld page for the Golomb Ruler for all the theory you can eat. There's been some research in to this problem, and you may be able to find a paper on the topic.

Not forgetting that the problem example is not a true Golomb Ruler, since we're not able to get all 11 distance possibilities. If you can find a general solution for the Partial Golomb Ruler, you might get a paper out of it.

take everything

bnt wrote: »

Have a look at the Wolfram MathWorld page for the Golomb Ruler for all the theory you can eat. There's been some research in to this problem, and you may be able to find a paper on the topic.

Not forgetting that the problem example is not a true Golomb Ruler, since we're not able to get all 11 distance possibilities. If you can find a general solution for the Partial Golomb Ruler, you might get a paper out of it.

Thanks.
I think they are all Golomb ruler problems but some are perfect (the 6 unit problem) and some aren't (eg the one above).
The stuff in the link includes them all.
But what that link seems to be more bothered about is optimality (my headache just got worse ).

ie they are more concerned with finding the shortest ruler where n lines create pairs of different integer lengths (whether perfect or not obviously).
So i'm wondering if these guys have these problems (where "shortest" isn't even a constraint- and you're just solving for an easy given length and n lines) solved easily.
But yeah the link is just the hardest (optimal) version of all possibilities.
(The shortest ruler for n lines).

Thanks.

MoogPoo

i think I heard a similar problem, kinda similar anyway.

There is a rock that weighs 40 grams. It is dropped and breaks into 4 pieces. Using a two sided weighing scales (you know the ones that balance two weights) you can place some or all of the the pieces in the scales so that every possible weight difference from 1-40 grams can be measured. Whats are the weights of the four pieces.

Ficheall

Ans:

1 3 9 27

I'm not sure I see any real connection between the two problems though..

take everything

Ficheall wrote: »

Ans:

1 3 9 27

I'm not sure I see any real connection between the two problems though..

It's not hugely dissimilar.
That's an interesting answer- i wonder if it being

3^n (n being 0, 1, 2, 3)

has any significance.
How did you work it out?

MoogPoo

I dunno the ruler one has 1-11 so to get an interval of 1 you have to have a mark at 2(or 10). Then you start looking for an interval of 3...

For the rock its 40 grams so you start of the same. You have to have a block of 1g(or 39g) to get an interval of 1. Then you need an interval of 2, so you put it at 3.. Its kinda building up the same wayish.

yeah 3^n works for solution, like if you had a starting rock of 121g then you could get every interval with 5 rocks of 1,3,9,27,81. I havent heard any nice simple reason before though.

But this way kind of works, only to verify though I dunno how you could get the answer without knowing it and without trial and error. But anyway: If you represent the 4 rocks in base 3 with 1's and 0's where 1010 would mean use 27g, not 9, use 3, not 1. like 1111 means 1+3+9+27. Then 1111 would mean all rocks on one side only. Then if you had one rock on the other side it would look like 0010 on left, 1101 on right. So the difference would be 1101-0010=1021 base 3.

So then every nr. up to 40 can be written as some base 3 string. Like 24 would be 0220 and then you can always find two base 3 strings with only 1's and 0's to get that answer. Like 1000-0010 = 0220. So a 40 gram rock minus a 3 gram rock is a 24 gram rock. Thats kind of awkward but I think it works.

Pygmalion

take everything wrote: »

It's not hugely dissimilar.
That's an interesting answer- i wonder if it being

3^n (n being 0, 1, 2, 3)

has any significance.
How did you work it out?

So I can't get to sleep at all, and this problem for some reason fascinated me...

Here's code (in python) implementing a solution (for any size, not just 40, it assumes you have access to

rocks of every power of 3

of course).
This unfortunately can't be spoilered (or I don't know how), so don't read it if you want to figure out the problem.

Edit: Actually this isn't really a "solution", since the solution is the size of the rocks required, and I already knew those :P.
It gets you the heavier of the two arrangements of rocks required to get any value of N you give it, and the other one is trivial to get once you have the first.

I make no guarantees of correctness, but it worked with any values I tested with (and I used quite large values, with any combinations of digits that immediately sprung to mind as being potentially troublesome).

In general, to find the X and Y (X > Y; X, Y and X+Y only containing 1s and 0s) for a number N:

def getX(N):
    #Just make sure there's enough digits for this by adding a leading 0 at the start
    N.reverse()
    N.append(0)
    N.reverse()
    #Initialise X to 0, and set the last digit we saw to 0
    X = [0 for x in N]
    last = 0
    for i in range(0, len(N)):
        #Go through each digit
        if (N[i] == 2 and last != 2):
            #If it's the start of a string of 2s, go back to the last 0
            #Set the digit of X at this position to 1
            #Set every digit of X it sees along the way to 0
            j = i-1
            while(N[j] != 0):
                X[j] = 0
                j = j - 1
            X[j] = 1
        elif (N[i] == 1):
            #If the digit is a 1, set this position in X to be 1 also.
            X[i] = 1
        last = N[i]
    return X

This takes N and returns the value X.

Both as a list representing the digits in base 3

Subtracting N from X should give you Y.

Observations/method:

Any string of digits in N that begins with a 0, ends with a 2 and has only non-zero digits in between can be worked out as follows:
Go to the 0 that starts this string and set the corresponding digit in X to be 1, all other digits in X corresponding to something in this string will be 0.
Any 1s in this string will be 1s in Y, and the 2 that ends the string will become a 1 in Y.

A string of 1s that isn't followed by a two can be simply placed into X as is.

Any digits in X or Y which haven't explicitly been given a value are 0

The code basically does this, but in a kinda roundabout way, I started coding with faulty assumptions and then kinda hacked it to work when I realised what was wrong, instead of actually redoing the method :P.

3DataModem

MoogPoo wrote: »

I dunno the ruler one has 1-11 so to get an interval of 1 you have to have a mark at 2(or 10). Then you start looking for an interval of 3...

For the rock its 40 grams so you start of the same. You have to have a block of 1g(or 39g) to get an interval of 1. Then you need an interval of 2, so you put it at 3.. Its kinda building up the same wayish.

Not quite.

The ruler 1 interval could be between 5 and 6 ... doesn't have to be at the end of the ruler.

Also the rock you definitely don't need 1g... you could have 14g and 15g giving you a diff of 1g. Also what use is 39g?

take everything

MoogPoo wrote: »

yeah 3^n works for solution, like if you had a starting rock of 121g then you could get every interval with 5 rocks of 1,3,9,27,81. I havent heard any nice simple reason before though.

But this way kind of works, only to verify though I dunno how you could get the answer without knowing it and without trial and error. But anyway: If you represent the 4 rocks in base 3 with 1's and 0's where 1010 would mean use 27g, not 9, use 3, not 1. like 1111 means 1+3+9+27. Then 1111 would mean all rocks on one side only. Then if you had one rock on the other side it would look like 0010 on left, 1101 on right. So the difference would be 1101-0010=1021 base 3.

So then every nr. up to 40 can be written as some base 3 string. Like 24 would be 0220 and then you can always find two base 3 strings with only 1's and 0's to get that answer. Like 1000-0010 = 0220. So a 40 gram rock minus a 3 gram rock is a 24 gram rock. Thats kind of awkward but I think it works.

[may contain spoilers]

Yeah i was looking at that and the 3^n does seem (to me at least) to be a unique series in this way.

In other words, as you say, adding, subtracting consecutive terms in all those permutations or just using individual terms by themselves seems to lead to this unique 1,2,3,4,5,6... progression.

^Edit: i'm conferring unwarranted specialness on this sequence tbh (apart from it working for this problem).
(As you say below, a simpler pattern of adding/subtracting the sequence 2^n also gives 1,2,3,4,5,6...). But it's interesting nonetheless. Maybe it's various arithmetic manipulations of various a^n sequences that has the special relationship with 1,2,3,4,5,6... i dunno.

This leads me to wonder if this 3^n only works for certain rock weights ie the ones that are sums of the sequence 3^n (from n=0 up):
So will it only work with rocks like these:
1
4
13
40
121 etc.

In that way the problem seems almost designed for this neat solution (which is a bit unsatisfying).

Or is there a less obvious way of getting consecutive numbers (1,2,3,4,5,6...) from more complicated patterns of addition and subtraction of other numbers. Like for 40 above, is this possible or are we to take it that this is the only solution? Indeed, as someone else pointed out, why do you have to start at 1 at all.

I'm not a mathematician so apologies if this comes across as elementary.

Edited for additional thoughts.

MoogPoo

yeah its the only solution. Choosing 1g first was just how you would find the solutions with trial and error. You could just take 14g and 15g to get a diff of one, then look for a diff of 2 etc. But if you do that you'll end up not being able to get some intervals. 1,3,9,27 is the only solution. It kind of makes sense that they should be spread out as much as possible the get the largest range as possible.

Like if it was just a regular weighing scales with just one side. Then you could represent every number wih 1g, 2g, 4g, 8g, etc. So every number up to 17 can be written as a combination of these. That solution is unique too for 4 rocks. So you can kind of see why it needs the grow exponentially. But for the double sided scales theres the extra option of subtracting weights as well as adding so it would make sense that the rocks would need to increase size faster than 2^n. So you could just guess 3^n and hope it works or something. Dunno though, Im sure theres a nice simple way of doing it though

equivariant

Here is a paper on the rock problem

http://www.maths.nuigalway.ie/~edwin/research/Bachet.pdf