An interesting little math riddle...

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Mathmagic
It's not as cool as that Criss Angel stuff.
Posts: 2926
Joined: Thu Nov 30, 2006 12:48 am UTC
Location: In ur fora posting in teh threads

An interesting little math riddle...

Postby Mathmagic » Mon Jul 30, 2007 5:19 pm UTC

So I ran across this problem, and I was trying to figure it out "mathematically" with equations and stuff, but it seems that a brute-force, guess-and-test method is about the only way to solve it.

-----------------------------------------------------------------------------------
Farmer Brown had a big rock that he used to measure grain on his balance scale.

One day his neighbor Farmer Green borrowed the rock, and when he returned it, it was broken into four pieces.

Farmer Green was very very sorry, but Farmer Brown thanked him for doing him a huge favor.

Farmer Brown said that now he can measure his grain in one pound increments starting at one pound all the way to forty pounds using the four rocks.

How much does each one of the four rocks weigh?
------------------------------------------------------------------------------------

To clarify, you need to be able to get each whole number value from 1-40 (inclusive) using some combination of each piece of the rock. This includes addition AND subtraction (you can put a 5 pound rock on one side of the scale, and a 3 pound rock on the other side of the scale, and it would effectively be a 2 pound rock on the heavier side of the scale, or you can put the 5 and 3 pound rock on the same side, and it would obviously be 8 pounds).

Anybody want to take a stab at it? Like I said, I've only managed to get semi-close using a guess-and-test/brute-force approach, but hopefully somebody here can come up with something a little more effective and/or efficient. :)
Axman: That, and have you played DX 10 games? It's like having your corneas swabbed with clits made out of morphine.
Pathway: cocks cocks cocks

User avatar
Walking Dave
Posts: 15
Joined: Sat Apr 21, 2007 4:39 pm UTC
Location: Massachusetts, USA

Postby Walking Dave » Mon Jul 30, 2007 5:32 pm UTC

My gut says the answer is
1,3,9,27
but I can't justify it any other way than brute force. I think I've seen the problem somewhere else before though. It's such an elegant solution, it has to be right. Right?

Cauchy
Posts: 599
Joined: Wed Mar 28, 2007 1:43 pm UTC

Postby Cauchy » Mon Jul 30, 2007 5:48 pm UTC

answer wrote:We see that since there are four pieces of rock, there are a total of 3^4 = 81 ways to arrange the pieces on the balance scales. Of the 81 arrangements, one of these involves not putting any rocks on, which gives a weight of 0, and of the rest, we can split them into equivalent pairs by, for each arrangement, switching those on the left side of the pan with those on the right, to create a "negative" of the first one. With this, we see that there are 41 distinct arrangements of rocks onto the scales -- these arrangements must produce all weights from 0 to 40, so, among other things, the total weight of the four pieces must be 40, and all 81 arrangements must produce all weights from -40 to 40.

Let's think of putting a piece of rock on neither side of the balance or on the same or opposite side as the grain in a different way: we start by making three copies of all the pieces of rock. We put one of each piece on the same side as the grain, and then we can choose to put 0, 1, or 2 copies on the opposite side, corresponding to putting that rock on the same side as the grain, neither side, or on the opposite side. Now, since we've put an extra 40 weight on the same side as the grain, we're trying to create any weight from 0 to 80 on the opposite side of the scale by putting 0, 1, or 2 copies of each of four different rock pieces on it. This is a question of turnary representation, and it's clear that the rock pieces must weigh 1, 3, 9, and 27 in order to create the requisite weights.

User avatar
Mathmagic
It's not as cool as that Criss Angel stuff.
Posts: 2926
Joined: Thu Nov 30, 2006 12:48 am UTC
Location: In ur fora posting in teh threads

Postby Mathmagic » Mon Jul 30, 2007 5:51 pm UTC

Cauchy wrote:This is a question of turnary representation, and it's clear that the rock pieces must weigh 1, 3, 9, and 27 in order to create the requisite weights


This isn't quite so clear to me, but maybe I'm just missing something. Could you explain how you reached that solution? I understand that there are x number of combinations/positions the rocks could be in, but I don't really follow that last little bit of your solution. :)
Axman: That, and have you played DX 10 games? It's like having your corneas swabbed with clits made out of morphine.
Pathway: cocks cocks cocks

User avatar
Yakk
Poster with most posts but no title.
Posts: 11058
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby Yakk » Mon Jul 30, 2007 7:55 pm UTC

mathmagic wrote:
Cauchy wrote:This is a question of turnary representation, and it's clear that the rock pieces must weigh 1, 3, 9, and 27 in order to create the requisite weights


This isn't quite so clear to me, but maybe I'm just missing something. Could you explain how you reached that solution? I understand that there are x number of combinations/positions the rocks could be in, but I don't really follow that last little bit of your solution. :)


Look at it as a number encoded in a base, each digit having 3 symbols. That is base-3. 1, 3, 9, 27 are the values of each digit in base-3.

A 4 digit base-3 number can encode any number up to 80 (3^4-1). However, because of how we are doing things, we are placing on the scales the number (an arbitrary 4 digit base-3 number) minus (1111 in base-3, aka 40). 0 to 80 minus 40 is -40 to 40.

User avatar
Mathmagic
It's not as cool as that Criss Angel stuff.
Posts: 2926
Joined: Thu Nov 30, 2006 12:48 am UTC
Location: In ur fora posting in teh threads

Postby Mathmagic » Tue Jul 31, 2007 4:07 pm UTC

I was really more confused by how he reached his solution... does it just have to do with combinatrics/permutations?
Axman: That, and have you played DX 10 games? It's like having your corneas swabbed with clits made out of morphine.
Pathway: cocks cocks cocks

User avatar
Yakk
Poster with most posts but no title.
Posts: 11058
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby Yakk » Tue Jul 31, 2007 4:29 pm UTC

mathmagic wrote:I was really more confused by how he reached his solution... does it just have to do with combinatrics/permutations?


I reached the same solution by looking at the problem, seeing that the rocks where digits of value -1, 0 and 1 in some possibly non-uniform base, and then trying the obvious solution to a 3-symbol number system -- base 3, or digit values of 1, 3, 9, 27. Proving that the answer was correct required noting that I could add 1111 to one side, thus producing a number from 0000 to 2222 or 0 to 80 -- a more natural and known way of looking at the values of the rocks. Now, the addition of 1111 (aka 40) was a virtual addition: it didn't actually happen -- so the actual values produced would be offset by 40. [0 to 80] minus 40 = [-40 to 40], which shows that the approach was sufficient.

Note that this doesn't prove that this solution is the best you could do. That would be an interesting problem:

You are allowed 4 rocks of any weight, and a perfect balancing scale.

Can you find 4 rocks that allow you to distinguish between all weights from 0 to 41 inclusive using a single balance? (I think not)

If so, how high can you go? (probably 40).

User avatar
Mathmagic
It's not as cool as that Criss Angel stuff.
Posts: 2926
Joined: Thu Nov 30, 2006 12:48 am UTC
Location: In ur fora posting in teh threads

Postby Mathmagic » Tue Jul 31, 2007 4:45 pm UTC

Please bear with me, but I still don't see how that solution is "obvious". If I missed something, please point it out, but I'm still not sure of how you just reached that solution. I realize that the solution is
1111
in base-3, but is it "obvious" because that's the *only* solution that would work if it was a base-3 system?
Axman: That, and have you played DX 10 games? It's like having your corneas swabbed with clits made out of morphine.
Pathway: cocks cocks cocks

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Postby Buttons » Tue Jul 31, 2007 5:28 pm UTC

Yakk wrote:You are allowed 4 rocks of any weight, and a perfect balancing scale.

Can you find 4 rocks that allow you to distinguish between all weights from 0 to 41 inclusive using a single balance? (I think not)

If so, how high can you go? (probably 40).

40:

Suppose without loss of generality that the object you'd like to weigh is going to be placed on the left scale. Each rock can go in one of three positions: the left scale, right scale, or off the scale. Thus there are 81 (3*3*3*3) ways to position the rocks.

1 such position involves placing no rocks on the scale, thus effectively weighing a zero-pound object. The other 80 positions can be broken up into mirrored pairs, where two positions A and B are identified if the rocks on the left in A are on the right in B, and vice-versa. Note that at most one of A and B can weigh a positively weighted item, since if A is heavier on the right, then B is heavier on the left. Therefore, at most 40 positive weights can be measured with four rocks.

User avatar
parallax
Posts: 157
Joined: Wed Jan 31, 2007 5:06 pm UTC
Location: The Emergency Intelligence Incinerator

Postby parallax » Tue Jul 31, 2007 5:47 pm UTC

You can solve it incrementally, although this doesn't guarantee an efficient solution (in terms of the highest weight measurable with a given number of rocks). If you only have one rock, it should be one pound. This allows you to weigh up to one pound of rock. If given another rock, you would want a 3-pound rock, because the 3-pound rock with the 1-pound rock still allows you to weigh 2 pounds (3-1) but also allows you to weigh up to 4 pounds. Now the third rock must give you 5 pounds, so you choose a 9-pound rock (5=9-3-1), which allows you to weigh up to 13 pounds. For the fourth rock, you choose 27 pounds (27=13+13+1 means 27-13=14).

Buttons has already proven that this configuration is also optimal.
Cake and grief counseling will be available at the conclusion of the test.

Cauchy
Posts: 599
Joined: Wed Mar 28, 2007 1:43 pm UTC

Postby Cauchy » Tue Jul 31, 2007 5:49 pm UTC

mathmagic, do you understand how we got to "we must be able to make any weight from 0 to 80 with two copies of each of the four pieces, using only one side of the scale?" I hope so, because I'll start from there.

more solution discussion wrote:Since we need to be able to make the weight 1, we need to have one of the rocks have weight 1. This allows us to make weights of 0, 1 and 2, so our next problem is making 3. So, another rock needs to have weight either 1, 2, or 3. But if we had new rocks that weighed 1 or 2, we'd be able to make weights that we've already made before. This is bad, because there are 3^4=81 ways to select some of the pieces of rock, and we're trying to make weights from 0 to 80, 81 distinct weights, so we can't have any repeats. The only way to make a weight of 3 without repeating weights is for the next piece of rock to have weight 3. This allows us to make all weights from 0 to 8. By a similar argument, the next piece must weigh 9, which allows us to make all weights up to 26, and then the last piece must weight 27. So this is the only way to do it, and these four rocks indeed let us get all weight from 0 to 80.


Edit: Whoops, forgot to white out the stuff in the quote. I don't know how that happened.
Last edited by Cauchy on Tue Jul 31, 2007 7:57 pm UTC, edited 1 time in total.

User avatar
Mathmagic
It's not as cool as that Criss Angel stuff.
Posts: 2926
Joined: Thu Nov 30, 2006 12:48 am UTC
Location: In ur fora posting in teh threads

Postby Mathmagic » Tue Jul 31, 2007 6:46 pm UTC

@Cauchy

Okay, I see where you're getting your solution now. :smile:

Thanks for the explanation.
Axman: That, and have you played DX 10 games? It's like having your corneas swabbed with clits made out of morphine.
Pathway: cocks cocks cocks


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 7 guests