Math Is Fun Forum

kneekill

Member

Registered: 2008-06-12

Posts: 1

Maths Problem - Weights

3280 KG of stone should be broken into 8 pieces such that we can weigh all weights from 1 KG to 3280 KG

help me solve this its urgent ..thanks a lot

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Maths Problem - Weights

One important trick to use here is to put weights on both sides of the scales.

For example, say you cut a 1kg weight and a 3kg weight from your stone.
You can measure 2kg using these two, by putting them on opposite ends.

---

Why did the vector cross the road?
It wanted to be normal.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Maths Problem - Weights

Suppose the weights are

, where

.

Let’s say that weights placed on the left-hand scale are positive while weights placed on the right-hand scale are negative. Then set of the total number of measurements you can get is

(Note that you can have negative measurements if you put more weights on the right than on the left.) This set A has at most 3[sup]8[/sup] = 6561 elements. One of these elements will be 0; of the rest, half will be positive and half negative – i.e. the number of positive elements is at most 3280.

So the problem reduces to this. We have |A| ≤ 6561 for any set {a[sub]1[/sub],…,a[sub]8[/sub]} with sum 3280; we must choose {a[sub]1[/sub],…,a[sub]8[/sub]} such that |A| = 6561.

So, how?

My idea is to consider the integers modulo 6561 as a vector space over the 3-element field {−1,0,1}, prove that this vector space has dimension 8 and find a basis of positive integers – which will then serve as the weights we want. So, how?

Last edited by JaneFairfax (2008-06-12 03:37:16)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Maths Problem - Weights

Got it. The weights you need are

. I’ll leave you to figure out why.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Maths Problem - Weights

I'd guess that kneekill is still years away from learning about vector spaces, and either way they're certainly not needed.

Simply jump in and try to find a solution. We need to be able to weigh 1kg, so making a weight of 1kg would be a good start.

Now we need to weigh 2kg. Making a 2kg weight would be one way, but it can also be done with a 3kg weight, as I showed in my previous post. The 3kg weight is better because along with the 1kg it also allows you to measure 3kg and 4kg.

The next barrier is 5kg, and we need an additional weight to measure this. From before, it seems like the highest possible "useful" weight will be the most helpful overall. If we put both out existing weights on the "negative" end of the scales, then a weight of 9kg is needed to measure 5kg.

With the three weights we now have, all weights from 1 up to 13 can be measured. For 14kg, another new weight is needed.

...

Continue on like that, and you should end up with a working solution (if one exists (which it does )).

Aah collision again

---

Why did the vector cross the road?
It wanted to be normal.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Maths Problem - Weights

I can’t prove this thoroughly yet – but you can look at it this way.

Every non-negative integer can be represented uniquely as a sum of powers of 3 with coefficients 0, 1, or 2. This is precisely the logic of the base-3 system – for example

and in base 3, the denary number 31 is written 1021.

In particular, all the numbers from 0 to 6560 can be represented uniquely in base 3 with coefficients from {0,1,2}. Now, what happenes if you change the coefficient set to {−1,0,1} instead? Clearly instead of integers from 0 to 6560, you are going to get integers from −3280 to 3280. I claim that there is a transformation from the base-3 system with coefficients from {0,1,2} to the system with coefficients from {−1,0,1} such that this transformation is a bijection from the integers from 0 to 6560 to the integers from −3280 to 3280. Hence every integer from −3280 to 3280 has a unique representation as sum of powers of 3 with coefficients −1, 0, or 1.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Maths Problem - Weights

What I mean is this:

Then Φ is a bijection (so A[sub]2[/sub] = {−3280,…,3280}).

Last edited by JaneFairfax (2008-06-13 00:09:56)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Maths Problem - Weights

Okay, here’s a proof using strong mathematical induction.

Prove that every positive integer can be written as a sum of powers of 3 with coefficients −1, 0, and 1. (NB: This is also true for negative integers; furthermore, the representation of each integer as such a sum is unique. For just his problem, however, we only need to prove what is stated.)

Since

the first three positive integers can be written in the given form. Suppose that for some positive integer n > 3, all positive integers less than n can be written in the given form.

Before we go on, we need two lemmas (preliminary results):

Lemma 1: If the highest power of 3 when a positive integer N is written in the given form is 3[sup]K[/sup], then the coefficient of 3[sup]K[/sup] must be 1.

Proof: If it were not the case, then

Lemma 2: If the highest power of 3 when a positive integer N > 3 is written in the given form is 3[sup]K[/sup], then

It follows that if

, then the highest power of 3 when N is written in the given form is less than 3[sup]K[/sup].

Last edited by JaneFairfax (2008-06-24 09:51:28)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Maths Problem - Weights

Let 3[sup]k[/sup] be the highest power of 3 such that 3[sup]k[/sup] < n. (If n = 3[sup]k[/sup] we are done.) Set

. If n = S we are done. Otherwise, either (i) n < S or (ii) n < S.

Consider

.

Since 0 < m < n, m can be written in the given form by the strong induction hypothesis. Now, note that

and

Hence we have

and so by the corollary to Lemma 2, the highest power of 3 in the given form of m is less than 3[sup]k[/sup].

Therefore n = 3[sup]k[/sup] + m can be expressed in the given form.
­

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Maths Problem - Weights

In this case consider

.

Now

In fact, we have that

otherwise

would be even.

Hence, by the strong induction hypothesis, m can be expressed in the given form.

Also,

and so by the corollary to Lemma 2, the highest power of 3 in the given form of m is at most 3[sup]k[/sup].

Therefore, once again, n = 3[sup]k+1[/sup] − m can be expressed in the given form.
­

MathsIsFun

Administrator

Registered: 2005-01-21

Posts: 7,711

Re: Maths Problem - Weights

Impressive!

---

"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

ZHero

Real Member

Registered: 2008-06-08

Posts: 1,889

Re: Maths Problem - Weights

Mind not if i didn't understand the question well but i think that every number has a unique representation in different bases!
Means, all numbers from 1 to 3280 can be represented in base-2 and in base-4 too.. right?
Then why only base-3 is chosen here??

---

If two or more thoughts intersect, there has to be a point!

ZHero

Real Member

Registered: 2008-06-08

Posts: 1,889

Re: Maths Problem - Weights

In simpler words..
Numbers from 1 to 3280 can also be represented in powers of 2, 4 or 5!
Then why 3 here?
(I'm really afraid if this is a silly question to ask!)

---

If two or more thoughts intersect, there has to be a point!