Brain Teaser No 1

Don,


My solution was much the same as Paul's, though I had to work out the equation he mentioned.

Ultimately lead to two equations

m+ 5 x n+ 50 x o < 300

and

59 x n + 31 x m = 49 x o

where n,m, and o are integers and total is the number of coins added.

Didn't use excel for mine though!

Matthew

One million can be expressed as the following,

10^6

which in terms of primes is

2^6 x 5^6

an number which contains as factors both 2 and 5 must end in zero so therefore the only options are 2^6 and 5^6 which are 64 and 15625.

Easier then I suspected.

Keep them coming Don.

Matthew

Mathew,

Easier then I suspected.

You got it, beautiful.

Lets credit Paul with providing the answer, because that makes looking for the elegant solution easier than expected.

Credits all round

Cheers

Don

Mathew, Paul,

and anybody else looking forward to a sleepless night!!!

The 'mathematical' approach !!!!!!!!!?????????

After a bit of 'trial and error' I discovered that in general it takes 1 move for each of the largest coins (ie the ones at the very bottom of the pile), 2 moves each for the next smallest (which would be the 2p coins but only if there were any 2p coins in the pile AND 50p coins, 4 moves each for the next smallest, 8 moves each for the next smallest, and so on.....

So, let the original pile consist of ( in decreasing order of size)

A @ 50p; B @ 2p...........

lets sleep on it a while.....

Cheers

Don

A 'conventional' ToH problem with N discs and three posts requires 2^N - 1 moves. If we label our discs 1 ... n where 1 is the largest and n the smallest then each disc gets moved 2^(n-1) times.

When another disc of the same size as an existing disc n is added to the pile then it adds another 2^(n-1) moves.

If the first pile contains a+1 5p, b+1 1p, c+1 20p, d+1 100p, e+1 10p, 1 2p, g+1 50p and the second pile contains an additional A 5p, B 1p G 50p, then,

(1) 59A + 31B - 49G = 0
(2) 5A + B + 50G <= 300
(3) A > 0, B > 0, G > 0
from 2 and 3,
(4) A < 49, B < 246, G < 6

The answer to the problem is then A + B + G. The 'mathematical' insight required is to prove there is only one set of A B G that satisfies these relation without guessing or searching exhaustively.

I think A = 1, B = 6 and G = 5... I just checked all possible values.

Paste this into a new file 'toh.cc' on a Unix box,

#include <iostream>

int main ()
{
   for ( int A = 1; A < 49; ++A )
       for ( int B = 1; B < 246; ++B )
         for ( int G = 1; G < 6; ++G )
         {
            if ( 5 * A + B + 50 * G >= 300 )
               break ;
            if ( 59 * A + 31 * B - 49 * G == 0 )
               std::cout << "A = " << A << ", B = " << B << ", G = " << G << "\n" ;
         }
   return 0 ;
}

Then compile with 'g++ -o toh -O toh.cc', and to run './toh'. It doesn't take long...

Paul

My solution FWIW

(But I did like both Paul and Mathew's solutions, especially Mathew's because he got similar equations to solve to mine.....)

Generally, the minimum number of moves required is, 1 move for each of the larges coins, 2 moves for each of the next smallest, 4 moves for each of the next smallest and so on.

Let the original pile comprise, in decreasing order,

A @ 50p; B @ 2p; C @ 10p; D @ £1; E @ 20p; F @ 1p; G @ 5p

Hence the total number of moves is = A + 2B + 4C + 8D + 16E + 32F + 64G (1)

This equals the total value of the pile = 50A + 2B + 10C + 100D + 20E + F + 5G (2)

Equating the above two equations gives 31F + 59G = 49A + 6C + 92D + 4E (3)

The number of coins is now doubled by adding some 50p; 1p; and 5p coins, to say

A + a @ 50p; B @ 2p; C @ 10p; D @ £1; E @ 20p; F + f @ 1p; G + g @ 5p

For the new value to equal the new number of moves we can write

31(F + f) + 59(G + g) = 49(A + a) + 6C + 92D + 4E (4)

(4) - (3) gives 31f + 59g = 49a

Given the limit of £3 on the value of the new coins means that trial and error soon shows that the only acceptable solution is

a = 5; f = 6 and g = 1

This means that 12 new coins were added and there were 12 originally, namely

2 @ 50p; 1 @ 2p; 1 @ 10p; 1 @ £1; 3 @ 20p; 1@ 1p; 3 @ 5p

Well, I hope Ihaven't made any typos

Cheers

Don

OK, lets use oranges instead.

I watched a fruit seller setting up his market stall the other day. He had a stack of boxes, each containing the same number oranges. He used the entire contents of the first box to make a rectangle of oranges to make the base of a stack.

He then used the contents of the other boxes to build up the stack, layer by layer. Each layer was a rectangle, one orange shorter and narrower than the layer beneath it.

Of course, the top layer SHOULD have a consisted of a single row of oranges, but the fruit seller was one orange short of being able to complete the stack. That’s when he noticed me watching him and he made some silly, Ann Robinson type, joke about being 'one orange short of a fruit basket'. "spot on, mate" was all I could say.

Afterwards I realised that even though I hadn't counted the oranges, I knew how many there were in each box .

So do you………….

Cheers

Don

Don,

I have the answer but I will let Paul have a go at this before spilling the beans as it will make it easier to prove. My approach was really ugly and involved meesy spreadsheets.

Now, if you can proof that the solution is unique I will be terribly impressed.

cheers

Matthew

Don,

I saw the same green grocers this morning and he had got the hang of this pyramid building and was trying his hand at apples, this time however he was over and had spare, which he gave to me. I managed to upset him when I started juggling with them, not being a very proficent juggler, I drop them and had to make a quick escape so didn't have time to see how high the tower was, didn't matter though.

How high was the pyramid?

Matthew

Don,

This one is killing me - hint please! If I
understand you correctly:

sum i=1,...,n-1 (n-i)(m-i) = (N-1)nm +1
n rows, m cols, N boxes, n levels

has a unique solution?
-Dan

[This message was edited by d marsh on TUESDAY 12 November 2002 at 18:11.]

Matthew,

Very sporting of you to hold back on the answer to give others a chance.....looks like Paul R has retired to his study to think, or simply thrown the towel into the ring and walked away....

Don.....if you can proof that the solution is unique I will be terribly impressed.

Standby to be terribly impressed............or better still, i'll wait a bit longer......you might figure out the unique solution. I am going to give our friend from Colorado a hint. This might help you find that unique solution.

Cheers

Don

PS Mathew, I presume you have a famous naim in mind?

Hi d marsh.

You asked for a hint to relieve your headache.

Assume the incomplete row at the top has R oranges in it. It should have had R+1 oranges, but it only has R.

This should get you started. But be warned......I found another headache had to be overcome on the way to the solution. Like all these things that do your head in, the solution hits you right between the eyeballs when you see it........until then, however, you have a headache and I seem like a smugg b*****d....

However, when you do see the answer, you don't half enjoy it, and i'm no longer smugg. A b*****d yes, smugg no. Have fun !!!

Cheers

Don

James (and any others out there)

my original 'fruit-seller' teaser said

He then used the contents of the other boxes to build up the stack, layer by layer. Each layer was a rectangle, one orange shorter and narrower than the layer beneath it.


This means he used ALL the oranges in ALL the other boxes of oranges to complete his stack. ie the bottom rectangle comprises one whole box of oranges, in James' case 160 oranges. The rest of the pyramid (indeed the whole of the pyramid) comprises a WHOLE NUMBER of boxes of oranges, except for being ONE ORANGE short on the top row.

In James' case I calculate the entire pyramid of 10 layers, comprised 715-1=714 oranges. But if one box contains 160 oranges (ie the bottom layer)the pyramid can only contain

320; 480; 640; 800......oranges. Not 714 oranges

Sorry James. I hope my amendment makes things clearer.

Cheers

Don

Don,

If R is the number left in the last row, then I think the problem is down to solving:

Rn(n+1)/2 + n(n+1)(2n+1)/6 = Nn(R+n) + 1

where n is the number of layers, and N the number of boxes.

the left hand side is a 'simplification' of

R + (R+2)2 + (R+3)3 + (R+4)4 ... (R+n)n

Or am I making this unecessarily complicated. Short of randomly guessing combinations of R and N, I cant think of an easy way to solve this and then there's the issue of uniqueness.

cheers

Dan

I'm stuck in the Netherlands all week and I've only just seen this. I have a neat solution but it won't fit in this gap.

Paul

Don

I have found an answer by trial and error in a spreadsheet, using the equations previously mentioned. However, I cannot find a "neat" solution, nor can I prove that my answer is unique.

I'm looking forward to the explanation!!

STEVE D

James numbers work and solve the equation I gave above, but there's also a trivial solution:

number of boxes = 1, 4 oranges/box

-dan

but there's also a trivial solution

Neat !!

Don

I have a neat solution but it won't fit in this gap

Change of name to Paul Fermat Ranson

Cheers

Don

I'm looking forward to the explanation!!


Well, my solution involves demonstrating that ALL the terms on each side of an equation incorporate a factor of 6. For all but ONE term, this is obvious because these terms all INCLUDE a multiplier of 6 anyway. It follows that the LAST term must also have a factor of 6.

What I'm no longer sure about is whether higher multiples of 6, eg 12 would allow a solution.

If anybody can demonstrate another solution than XX (insert a famous naim, which most of us have deduced anyway) then I shall have to apologise for my claim to a unique solution. Given Dan's 'trivial' solution of 4, which I hadn't spotted, I feel that an apology is due anyway......it just might have to be a lot bigger if there are lots of other solutions.

Cheers, (with apologies to all)

Don

Let the incomplete Row at the top have R oranges.

The top rectangle (if FULL) should have been 1x (R+1) oranges

Let the total stack comprise L Layers.

Total number of oranges in a FULL stack would be

1 * (R+1) + 2 * (R+2) + 3 * (R+3) +…..+ L * (R+L)

This can be simplified to

(1 + 2 + 3 + …..+ L)R + (1^2 + 2^2 + 3^2 +……+ L^2)

and summed to give

(1/2)L(L + 1)R + (1/6)L(L + 1)(2L + 1).......... equation (1)

The bottom layer contains L * (R + L) oranges, and this equals one box.

To complete the stack we need B boxes plus one orange ie

BL(L + R) + 1..............equation (2)

equations 1 and 2 are equal, hence

(1/2)L(L + 1)R + (1/6)L(L + 1)(2L + 1) = BL(L + R) + 1

multiply by 6

3L(L + 1)R +L (L + 1)(2L + 1) = 6BL(L + R) + 6............ equation (3)

notice in equation 3 that L goes into every term except the 6

it follows that L must go into the 6 also.

Hence L = 1, 2, 3 or 6

trying 1,2 and 3 gets nowhere.

trying L = 6 gives

3*6*7*R + 6*7*13 = 6*B*6(6 + R) + 6

or

R = 6(2B - 5)/(7 - 2B).............equation (4)

Now one solution to this is B = 3 and R = 6

hence each Box, which contains L(R + L) oranges, having 72 oranges

Now, I'm no longer sure that equation 4 has only one unique solution and I hope to L that I haven't made any typos !!

All comments gracefully received

Cheers

Don

Don,

I'm amazed you could figure all that out just staring at the grocer! One comment - you wrote "trying 1,2 and 3 gets nowhere", but L=1is the 'trivial' solution (R=0). I think the fact that L must divide 6 rules out pyramids larger than 6 high. I haven't checked L=2 and 3, but
I take it there are no integer solutions to these equations?
cheers,

Dan

quote:

---

(1/2)L(L + 1)R + (1/6)L(L + 1)(2L + 1) = BL(L + R) + 1

I hope to L that I haven't made any typos !!

---

Dont think so - we arrived at the same formula if you replace L with n and N with B then you get the formula I posted:

Rn(n+1)/2 + n(n+1)(2n+1)/6 = Nn(R+n) + 1

The step on noticing that n( or L) needs to divide 6 is the key though.

cheers

dan

but there's also a trivial solution: L=1

I hadn't spotted that one, as I said above. On reflection, the story line makes it clear there was more than one box of oranges. This, in effect, rules out the trivial solution. I realise this is nit-picking, so the plaudits for spotting the 'trivial' solution still stand IMHO.

cheers

Don

Naim have just had a BIG clearout of the old style kit. As a result, I have just received three crates of power amps. One crate is full of NAP180s another is full of 250s and the last is full of 135s. There are 12 amps in each crate (this is irrelevant) and I paid £1 each, plus delivery and they are all sonically perfect. Dream on Don….

Unfortunately, the labels have come off the crates and none of the amps have serial numbers or model numbers. I have been told by Naim that the 180s each weigh 6kg, the 250s each weigh 7kg and the 135s each weigh 8kg.

Now, I have some scales (direct reading ones, not the old fashioned balance type) that read accurately up to 30kg in 1kg intervals. I wish to use these scales to determine which amps are which.

What's the minimum number of weighings I need to do this.

Cheers

Don