Hey Bazza...I am so totally hopeless in maths - but can all that above be represented in a formala of some kind? Formulae always impress me.
AR
Alas, all mathematics is not algebra, although it seems like it is at times.Originally Posted by arosar
There is a formula for the staircase problem, but it does involve sigma notation.
Last edited by Barry Cox; 13-02-2004 at 06:49 PM.
So einfach wie möglich, aber nicht einfacher - Albert Einstein
Anyone going to have a go at this one or is everyone mathed out for now? If I don't hear anything for 2 days I'll post the general answer for nxn configuration as well as the value for n=50.Originally Posted by Barry Cox
(Shaun, a cute programmatic solution should be possible via recursion.)
Last edited by Barry Cox; 16-02-2004 at 09:36 PM.
So einfach wie möglich, aber nicht einfacher - Albert Einstein
I've been having a half-hearted stab at this one but haven't solved it yet.Originally Posted by Barry Cox
Mathematics is quite funny ain't it? I remember back in high school I did Physics and this fella in class compained to our teacher. He says, "Sir, we don't wanna solve that problem cos it's too hard. It's got too many numbers in it." So the teacher turns around and gives us a new problem. This time with no numbers but only letters and funny symbols! Mate, it was virtually 'impossible' to solve.Originally Posted by Barry Cox
Have you heard of that Harvard comp at all? Apparently it's the most prestigious.
AR
Yes, Median score = 1 out of a possible 120.
Not enough spare time, sorry Barry.
That's surprising. Is this the Harvard-MIT Mathematics Competition for high school kids we're talking about?Originally Posted by Jeo
So einfach wie möglich, aber nicht einfacher - Albert Einstein
No, its not that one. I'll try and find out which Harvard test it is later.
Unfortunatey, no solvers this time, so it's time to put you out of your misery.Originally Posted by Barry Cox
To start with it's pretty easy to see (by just counting row by row) that the number of unit squares in an nxn configuration is
1 + 2 + 3 + ... + (n-2) + (n-1) + n
lets symbolise this as Sig(q=1,n)[q]
There are a few ways to look at this puzzle but the one that makes the most sense to me is to consider every rectangle (let's call squares, rectangles for the duration of this post) as being defined by its bottom left and top right corners. Then if you fix the bottom left corner as the very bottom left of the staircase (as drawn above) then you have as many rectangles as you have unit squares.
Then if you consider the diagonal 1 unit square up and 1 to the right of the very bottom and fix these as the bottom left corner of every rectangle it can be seen that the number of rectangles you can make is equal to the same as the number of unit squares in the n-1 case for each one.
Likewise moving up one more diagonal you have 3 potential bottom left corners forming the same number of rectanges as in the n-2 case and so on and so forth until you get to the nth diagonal (the treads of the staircase) which have n cases forming the bottom left corner of only 1 rectangle each.
Thus we have the following general answer
F(n) = 1 x Sig(q=1,n)[q] + 2 x Sig(q=1,n-1)[q] + 3 x Sig(q=1,n-2)[q] + ... + (n-2) x Sig(q=1,3)[q] + (n-1) x Sig(q=1,2)[q] + n x Sig(q=1,1)[q]
This can be more simply expressed as a double sigma
F(n) = Sig(p=1,n)[p x Sig(q=1,n+1-p)[q]]
Some simple cases are...
F(2) = 1 x (1 + 2) + 2 x 1 = 3 + 2 = 5
F(3) = 1 x (1 + 2 + 3) + 2 x (1 + 2) + 3 x 1 = 6 + 6 + 3 = 15
For n = 11 the answer is F(11) = 1001 (Significant in the context of the listserver group where the problem was sourced as it was the 1001st problem of the series!)
For n = 50 the answer is F(50) = 292,825
These are a little tedious to work out by hand but can be readily calculated wth Excel. For example, enter the formula =row() is cell A1 and =A1+row() in A2. Then copy A2 and paste into A3:A50. (This sets the A column up with the number of unit squares in every nxn configuration from 1 to 50.)
Then set B1 =(51-row())*A1 and copy and past that into B2:B50. Then set B51=SUM(B1:B50) and there you have it.
Last edited by Barry Cox; 22-02-2004 at 11:27 PM.
So einfach wie möglich, aber nicht einfacher - Albert Einstein
That would depend on the judging criteria. Are these solved or unsolved problems? I would think, in the main, unsolved problems must be considered "harder" than solved ones. Then there is the question, ARE they solveable in a closed form? Is it possible to prove that it is solveable/unsolveable, etc.Originally Posted by arosar
Anyway, of solved problems, Fermat's Last Theorem is my favourite. It has to be the granddaddy of tricky problems which eluded solvers for generations. Stickly speaking it is a proof, not a puzzle though, so perhaps it wouldn't qualify.
So einfach wie möglich, aber nicht einfacher - Albert Einstein
Unsolved.
See, this is where I got a bit lost right. This fella was yappin' on about 'conjectures' and 'theorem'. One from memory was some Riemann something.
(Actually, only just now I realise that there is a direct link to the story. So read for yourself mate. It's quite interesting. http://afr.com/articles/2004/03/04/1078378902714.html)
AR
Thanks for the link, interesting book. I think I'd heard about it before, but hadn't seen a review.Originally Posted by arosar
For more info on the Riemann Zeta Function, you can look here http://mathworld.wolfram.com/RiemannZetaFunction.html
10 years ago FLT would have made the list but that would have been shown up as bogus as it was proved and many other conjectures remained unproved. It is the ones which stir the imagination which make the list not necessarily the hardest. The other problem is how can you judge which puzzles are harder than others when the solutions are unknown? I'm not sure you can.
So perhaps it should be called Seven Unsolved Puzzles.. and not The Seven Greatest Unsolved Puzzles... :p Still one for the birthday list, I think.
So einfach wie möglich, aber nicht einfacher - Albert Einstein
There are currently 1 users browsing this thread. (0 members and 1 guests)