Rooks
Eric and Rachael Farmer
(save one, I think) gave the same solution. It was a correct answer- but to
a different question, in my opinion. See what you think:
In how many ways can you move a rook from the lower-left square of an empty
(except for the rook!) chessboard to the upper-right square, if you can only
move the rook up or to the right?
Eric Farmer
Jonathan Dushoff
I wonder if this response requires spoiler space.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
I am going to guess that the answer that almost everybody gave was 14C7
= 3432. This is the correct answer if you differentiate routes only by
steps and not by the way that these steps are divided up into rook's
moves. I would agree that this is not the correct answer to this
question.
If you differentiate by moves, I think the answer is a lot larger.
Jonathan Dushoff
Olaf
If I understand the puzzle correctly then I think the
answer is as follows: It takes 16 steps to move the
rook from the one corner to the other. This doesn't
depend on the path taken. 8 of these steps
are up, and 8 are to the right. So the number of possible
pathways is equal to
| 16 |
| 8 | = 16!/(8! * 8!) = 12870
excuse me if I'm repeating the solution given in the other
tread.
olaf
Jonathan Dushoff
: I am going to guess that the answer that almost everybody gave was 14C7
: = 3432. This is the correct answer if you differentiate routes only by
: steps and not by the way that these steps are divided up into rook's
: moves. I would agree that this is not the correct answer to this
: question.
Numerical Spoiler:
.
.
.
.
.
.
.
.
.
.
.
.
: If you differentiate by moves, I think the answer is a lot larger.
In particular, based on a simple computer program, I think the answer is
470,010.
I don't know a good way to do this analytically.
Jonathan Dushoff
Olaf
instead of moves. OK. Mhm, don't know about the answer
about the steps, but what is meant by 14C7? It's a
mathematical notation I don't know?
Your answer 470.010 is a lot more than my 12870.
Any objections against the line of reasoning I used
to get 12870?
olaf
Nick Wedd
sp...@cs.utwente.nl> writes
>Your answer 470.010 is a lot more than my 12870.
>Any objections against the line of reasoning I used
>to get 12870?
Your answer assumes that the rook only ever moves one square at a time,
Jonathan's assumes that it can make any right- or up- rook move.
Your answer also contains a mistake: it should be 14!(7! * 7!) = 3432,
not 16!/(8! * 8!) = 12870.
Nick
--
Nick Wedd ni...@maproom.co.uk
Nick Wedd
<dus...@gate.sinica.edu.tw> writes
>I wrote earlier:
>
>: I am going to guess that the answer that almost everybody gave was 14C7
>: = 3432. This is the correct answer if you differentiate routes only by
>: steps and not by the way that these steps are divided up into rook's
>: moves. I would agree that this is not the correct answer to this
>: question.
>
>Numerical Spoiler:
>
>.
>.
>.
>.
>.
>.
>.
>.
>.
>.
>.
>.
>
>: If you differentiate by moves, I think the answer is a lot larger.
>
>In particular, based on a simple computer program, I think the answer is
>470,010.
>
>I don't know a good way to do this analytically.
I did it easily with a spreadsheet. Into the bottom left square I typed
"1". Into the cell above it, which happened to be I22, I typed
"=SUM(A22:H22)+SUM(I23:I30)". I copied this formula, which sets the
value of a cell to the sum of the eight values below it and the eight to
the left of it, into all the other cells. Here is the result:
64 320 1328 4864 16428 52356 159645 470010
32 144 560 1944 6266 19149 56190 159645
16 64 232 760 2329 6802 19149 52356
8 28 94 289 838 2329 6266 16428
4 12 37 106 289 760 1944 4864
2 5 14 37 94 232 560 1328
1 2 5 12 28 64 144 320
1 1 2 4 8 16 32 64
dmo...@xraysgi.ims.uconn.edu
Jonathan Dushoff <dus...@gate.sinica.edu.tw> wrote:
|...
|In particular, based on a simple computer program, I think the answer is
|470,010.
|
|I don't know a good way to do this analytically.
|
The wrong answer 14C7 is the coefficient of x^7y^7 in (x+y)^14. Similarly,
the number of ways of getting from one corner to another in n rook moves will
be the coefficient of x^7y^7 in
(x + y + x^2 + y^2 + x^3 + y^3 + ...)^n.
Summing this over n tells us that the total number of ways will be the
coefficient of x^7 y^7 in
1/(1-x/(1-x)-y/(1-y)) = (1-x)(1-y)/(1-2x-2y+3xy).
1/(1-2x-2y+3xy) can be re-expanded as
1 + (2x+2y-3xy) + (2x+2y-3xy)^2 + (2x+2y-3xy)^3 + ...
and using the trinomial theorem on each of these terms gives an answer of
sum((-3)^i 2^(12-2i) (4T(i,7-i,7-i)-4T(i,6-i,7-i)+T(i,6-i,6-i)), i=0..7)
where T(a,b,c) = (a+b+c)!/(a!b!c!) if a, b, c are all nonnegative,
0 otherwise.
Doing the sum yields your answer of 470010.
--
David Moews dmo...@xraysgi.ims.uconn.edu
il...@isgtec.com
>A relative of mine was a precocious child. On her seventh birthday, the
>fifth of the month, she proclaimed "This is the first year in my life
that
>no other fifth day of a month falls on the same weekday as my
birthday".
>Annoyingly, she was right. When was she born?
>
>[Posted Dec-04-1999 to rec.puzzles www.deja.com]
>
SPOILER
October 5, 1897.
October is the only month in which the day of the week occurs twice
on a regular year and once on a leap year. This means that the year
1900 must have occurred in between, and the birth year is thus 1897.
__/\__
\ /
__/\\ //\__ Ilan Mayer
\ /
/__ __\ Toronto, Canada
/__ __\
||
Sent via Deja.com http://www.deja.com/
Before you buy.
Vish
first: to move from square one to square eight it only takes seven moves
second : nobody said that the rook is limited to one-square moves
Olaf <donk-not-...@cs.utwente.nl> wrote in message
news:3847C4C5...@cs.utwente.nl...
> Ah right, now i understand what is meant by steps
> instead of moves. OK. Mhm, don't know about the answer
> about the steps, but what is meant by 14C7? It's a
> mathematical notation I don't know?
>
> Your answer 470.010 is a lot more than my 12870.
> Any objections against the line of reasoning I used
> to get 12870?
>
> olaf
>
>
> Jonathan Dushoff wrote:
> >
> > I wrote earlier:
> >
> > : I am going to guess that the answer that almost everybody gave was
14C7
> > : = 3432. This is the correct answer if you differentiate routes only
by
> > : steps and not by the way that these steps are divided up into rook's
> > : moves. I would agree that this is not the correct answer to this
> > : question.
> >
> > Numerical Spoiler:
> >
> > .
> > .
> > .
> > .
> > .
> > .
> > .
> > .
> > .
> > .
> > .
> > .
> >
> > : If you differentiate by moves, I think the answer is a lot larger.
PaulDH
Martin Bernhauer
>
>The wrong answer 14C7 is the coefficient of x^7y^7 in (x+y)^14. Similarly,
>the number of ways of getting from one corner to another in n rook moves will
>be the coefficient of x^7y^7 in
>
> (x + y + x^2 + y^2 + x^3 + y^3 + ...)^n.
>
>Summing this over n tells us that the total number of ways will be the
>coefficient of x^7 y^7 in
>
> 1/(1-x/(1-x)-y/(1-y)) = (1-x)(1-y)/(1-2x-2y+3xy).
>
>1/(1-2x-2y+3xy) can be re-expanded as
>
> 1 + (2x+2y-3xy) + (2x+2y-3xy)^2 + (2x+2y-3xy)^3 + ...
>
>and using the trinomial theorem on each of these terms gives an answer of
>
>sum((-3)^i 2^(12-2i) (4T(i,7-i,7-i)-4T(i,6-i,7-i)+T(i,6-i,6-i)), i=0..7)
>
> where T(a,b,c) = (a+b+c)!/(a!b!c!) if a, b, c are all nonnegative,
> 0 otherwise.
>
>Doing the sum yields your answer of 470010.
>--
>
3432.
Asume the following: take the symetry-axis of the problem, the
dioganel up-left to down right.
First step: Take the corner up-left (A8):
there is only one way to get there, moving seven up, and , remember
the symetry, there is only one way too to reach the final point,
right-up, moving seven right.
taking the next square (B7):
you can move on seven different paths to this point and with seven
different path to H8, this makes 49 ways through this point, and so
on.
the values of the square are equal to the binominal coefficients 7
over i, just add the square of this values and you get 3432 = 2*(1^2
+ 7^2 + 21^2 + 35^2).
Martin
PaulDH
On her 38th birthday, Harriet said "This is the first year of my life in
which my birthday is the only first day of a month to fall on this
particular day of the week." Since that day, nobody could have correctly
spoken those words on their 38th birthday.
When was she born?
Olaf
already the hard part for me ;)
but the second point, are we counting pathways or
move-sequences?
Jonathan Dushoff
: >Doing the sum yields your answer of 470010.
: >--
: >
: sorry, but if you count the routes only, then the solution is still
: 3432.
I don't know why you're sorry. Everyone has agreed that if you count
the routes only the number is 3432, and if you count the ways those
routes can be broken into rook moves the number is 470,010.
Jonathan Dushoff
PaulDH
before a leap year. 38 years later, somebody responds to his post. In the
meantime, alt.brainteasers posts 452 variations on P's puzzle. On his 35th
birthday, P 'goes postal' and assassinates 14 members of an innocent
newsgroup. What day was P born on?
David R. Conrad
>P.S Another valid solution is to go from 1797 to 1804 because 1800 is still
>a century year. It's a little harder to argue further back 1697 to 1704
>(although 1700 is a century year sources indicate the Gregorian calendar
>began on 9/14/1752 so anything before that is out of bounds)
Sources are notoriously unreliable, and I wouldn't listen to them
if I were you. The Gregorian caledar was adopted in the late 16th
century in Catholic countries (156x? I forget), and it was only in
Protestant countries, such as England and her colonies, among others,
where the calendar reform was put off until 1752.
ObPuzzle: Why did the Protestants have to skip (only) one day more
than the Catholics in order to get the calendar back into line?
--
David R. Conrad <d...@adni.net>
Silent leges inter arma