# Puzzle



## pjk (May 18, 2008)

A robot is located at the top-left corner of the grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below)*.








How many possible unique paths are there?
_(Note: Answer must be an exact, decimal representation of the number.)_


----------



## blgentry (May 18, 2008)

The answer is (highlight to read):

28

The solution is actually very elegant. Thanks for posting this. 

Brian.


----------



## deno (May 18, 2008)

Darn blgenrty beat me to it.
28 = (x+1)*(y+1) = (6+1)*(3+1)=7*4=28<-highlight


----------



## Lucas Garron (May 19, 2008)

8C2=(8*7)/2=28


----------



## blgentry (May 19, 2008)

Lucas and Deno:

Care to explain your methods? In Lucas' case, I'd like an explanation of the notation too. I solved this by inspection and found a sequence that it followed.

Brian.


----------



## pjk (May 19, 2008)

Okay, same question, but what about for a grid that is say 65x53?


----------



## cmhardw (May 19, 2008)

pjk said:


> Okay, same question, but what about for a grid that is say 65x53?



I don't know how to hide the text such that you need to highlight it, but for a 65x53 grid starting at the top left and ending at the bottom right there are:

116!/(64!*52!) = 3.32*10^33 unique paths

--edit--
For a j x k grid there are (j+k-2)!/[(j-1)!*(k-1)!] unique paths
--edit--

Chris


----------



## Lucas Garron (May 19, 2008)

Since we're not hiding our answers anymore, lemme show off Mathematica:
3315373647943114597923661301589195

http://mathworld.wolfram.com/BinomialCoefficient.html
(j+k-2)C(j-1)=(j+k-2)C(k-1)
There are j+k-2 moves, and you can choose j-1 of the moves to be to the right (WLOG , the side of length j is horizontal), and the others have to be down...
(Or you can choose k-1 to be down, and the other have to be to the right.)

Chris has the correct explicit closed-form expression.


----------



## cmhardw (May 19, 2008)

Lucas, I have to admit reading your post gave me a "duh!" moment. I honestly would not have ever thought of that problem as a combination. I thought of the problem (the original 3x7 grid) as permuting 2 D's (for down) and 6 R's (for right) into a string of letters. I am permuting 8 objects, in two groups of indistinguishability (D's and R's). So I get 8!/(6!*2!) to account for the groups of indistinguishable letters.

I can see the (j+k-2)C(j-1) or (j+k-2)C(k-1) way now that you mention it, but I wouldn't have thought of it that way.

Neat!

Chris


----------



## pjk (May 19, 2008)

I see. Interesting. I was always wondering how to handle these where it restricts the movement of the "robot". Thanks Chris and Lucas.

Lucas, I am thinking about getting Mathematica. I've wanted it for along time, but didn't think I should spend my money it. How much is it these days? How much is an upgrade to the latest version?

Edit:
We should have a daily puzzle posted here. These are fun!


----------



## brunson (May 19, 2008)

Pat,

You should be eligible for a student license, the full version for non-students is exhorbitantly expensive, like $2500. There are different student licenses, you should read the details, but you can get a six month time limited copy for less than $50 or the non-limited license for around $130, I think.

It's a great program, it's in my top 10 consumer software applications ever written. There are other symbolic math packages that are free and open source. Of course none of them have the polish or the complete features of Mathematica, but some are very cool.


----------



## badmephisto (May 19, 2008)

Alright, lets see if we can solve it another way  (but clearly 28 is the right answer just from my head. Doing it by choosing 2 from 8 is obvious to me)
Clearly, if we define number of ways to get to position i,j as P[i,j], (row,column), then it must be that there is a simple recurrence relation that leads to the answer:

P[i,j] = P[i-1,j] + P[i,j-1]
P[1,0] = 1
P[0,1] = 1

This is just due to the fact that you can get to position i,j by getting there from top OR from the left. 

If you solve for the recurrence relation you can probably figure out the formula for arbitrary i,j (Its just the Pascals triangle). I will just do brute force evaluation of P for each cell:

0 1 1 1 1 1 1 
1 2 3 4 5 6 7
1 3 6 10 15 21 28

hence the answer is P[2,6] = 28 because 28 = 21 + 7.


----------



## andrewvo1324 (May 19, 2008)

Can anyone give me a deep explanation to this problem as i would like to learn how to solve similar problems like this for future references. I'm not sure if this math is to high for my knowledge but i am in 7th grade math going to algebra next semester and i make 90-100 every report, as im pretty good in math. 

So yea can some please explain throughly? Thank you.

Best thanks,

Andrewvo1324 

P.S and so happens were learning Combination,permutations, and stuff ehh

If i may go at it. Scince The robot can go right or down at any time. Going from deno equation "28 = (x+1)*(y+1) = (6+1)*(3+1)=7*4=28" Robot can go RIGHT 6 times and you add 1 because your taking 1 step? and then 3 times down +1 for 1 step then you multiply to get total combonations?


----------



## cmhardw (May 19, 2008)

andrewvo1324 said:


> Can anyone give me a deep explanation to this problem as i would like to learn how to solve similar problems like this for future references. I'm not sure if this math is to high for my knowledge but i am in 7th grade math going to algebra next semester and i make 90-100 every report, as im pretty good in math.
> 
> So yea can some please explain throughly? Thank you.
> 
> ...



Hi Andrew,

While I think Lucas' solution is definitely the most elegant, I think my solution is a bit more intuitive if you're just learning about permutations and combinations. For this solution you don't need to use combinations.

Imagine you are going to write a directions sheet to feed into the robot to tell it how to move to get from the top left to the bottom right. We're going to solve the 3x7 grid first, then the ones in general.

First think of any solution to our 3x7 grid. Say we go right 6 times then down twice. So you have to give the robot 8 directions to get it to the bottom left. Now think of a sheet of paper wth 8 blanks on it, and in each blank you will write either a letter "R" or a "D" to tell the robot to get either right or down. Now you *must* for any solution set write 2 D's and 6 R's, but they can be arranged in different ways. This is because the top left space is 2 rows above and 6 columns left of the final ending space. Think of this as having a word bank of 2 letter "D"'s and 6 letter "R"'s. Once you write a letter down you cross it out from the word bank and you can't use it again.

Now the problem is reduced to how many different anagrams are there from the "word"
DDRRRRRR

This is kind of like problems where they say, how many anagrams are there for the word MISSISSIPPI.

So for our word, DDRRRRRR, we have 8 letters. So let's permute all 8 letters as if they were all distinct. This gives us 8! different anagrams. The problem is that the two D's are indistinguishable, meaning we can't tell one from another. There are 2! = 2 ways to arrange 2 letters if there were distinct. This means you have counted twice as many anagrams as there really are in terms of how the D's can be arranged. Think of DRRRRRRD, and how this is not any different from switching the left D with the right D leaving us still with DRRRRRRD.

Do the same thing for the R's. There are 6 R's and there are 6!=720 different ways to arrange 6 things. So this means you have not only overcounted the anagrams because of the D's but also because of the R's. You have counted each anagram 720 times too many because all the R's are indistinct.

Ok so take your 8! anagrams of DDRRRRRR and divide by (2*720) because you have counted the anagrams twice as many times as we should, and then 720 times too many. These compound to mean you have overcounted by 1440 times too many.

8!/[(2!*6!)] = 28 total ways for the robot to get to the bottom right.

For a j x k grid you have to give the robot (j-1) + (k-1) directions. If there are j rows and k columns then this means that (j-1) of these directions are D's for down and (k-1) of these are R for right. Now use the same process as above to get the formula.

Again Lucas' solution is much more elegant, but I think this is a more intuitive way to think about it that doesn't use combinations (even though the root of the problem is that you really should use combinations). Think of this as an intermediate level solution to the problem, but you still get the correct answer.

Hope this helps,
Chris


----------



## Johannes91 (May 19, 2008)

pjk said:


> We should have a daily puzzle posted here. These are fun!


You didn't seem to mention where you got this problem from. http://treasurehunt.appspot.com/

Instead of copying puzzles from other sites to this forum, why not actually use those sites instead? Check out Project Euler, it has 194 problems at the moment and one new is added every week. The problem in this thread is #15 there, btw.


----------



## pjk (May 19, 2008)

Johannes91 said:


> pjk said:
> 
> 
> > We should have a daily puzzle posted here. These are fun!
> ...


Thanks Johannes. I actually pulled the puzzle off a blog I read. Have you solved all 194 yet?


----------



## masterofthebass (May 19, 2008)

http://projecteuler.net/index.php?section=scores&country=Finland

He's at 92%, which is 178 problems. He is #1 in Finland though


----------



## pjk (May 19, 2008)

brunson said:


> Pat,
> 
> You should be eligible for a student license, the full version for non-students is exhorbitantly expensive, like $2500. There are different student licenses, you should read the details, but you can get a six month time limited copy for less than $50 or the non-limited license for around $130, I think.
> 
> It's a great program, it's in my top 10 consumer software applications ever written. There are other symbolic math packages that are free and open source. Of course none of them have the polish or the complete features of Mathematica, but some are very cool.


I will look into it, thanks.


----------



## cmhardw (May 21, 2008)

masterofthebass said:


> http://projecteuler.net/index.php?section=scores&country=Finland
> 
> He's at 92%, which is 178 problems. He is #1 in Finland though



This list is already starting to consume me. I'm still up till 5:30am and have gotten 8 problems solved so far tonight 

I have virtually no knowledge of programming, so most of these problems I don't know how to do. But I am trying to find the ones that are more just number theory oriented, where I don't really need to know how to program to do them.

This list is fun,
Chris


----------



## genwin (May 22, 2008)

cmhardw said:


> masterofthebass said:
> 
> 
> > http://projecteuler.net/index.php?section=scores&country=Finland
> ...



If I am Chris Hardwick, i don't think i'll have that much of a problem learning the basics of programming.. and become a good one at that too... just a thought...


----------



## Lucas Garron (May 22, 2008)

Chris: Come on, it's not that elegant! I did exactly what you did, thought of it as DR strings. You just went into an explanation of the combinations formula (and its relation to permutations), while I gave a lazy, compact expression without explanation. 

Anyhow, who else wants to see a robot go down/right/away/dimension-4-positive-wardly/dimension-5-negative-wardly/dimension-6-left-wardly inside a 4x4x4x4x4x4 hypergrid? 
(Yes, that's a puzzle.)
(But I'm not telling you which puzzle [it's isomorphic to])


----------



## Stefan (May 22, 2008)

Revenge center states?


----------



## cmhardw (May 22, 2008)

StefanPochmann said:


> Revenge center states?



I am fascinated by this question, and I have no idea how to solve it to find the precise answer (how many distinct center states are there on a 4x4x4 without overcounting?).

I have used the following to estimate the probability of how many solved centers can you expect on a 5x5x5 for 1 of the center orbits. Yes this is for 5x5x5 and not 4x4x4 because of the fixed centers on 5x5x5.

(24 C n)*(1/6)^n*(5/6)^(24-n)

If you sum this expression from n=0 to n=9 you get a cumulative probability of approximately 99%, so most of the time you will have 9 or fewer centers solved (allowing for maybe none solved). By the way the expected value of the number of solved centers using this estimation is:

sum(n=0 to n=24 n*(24 C n)*(1/6)^n*(5/6)^(24-n)) = 4

So you can expect to have 4 centers solved in each center orbit, or 8 centers in total for a scrambled 5x5x5. Also, I do realize that this is an estimate. My strategy here is to assume that I simply throw center stickers onto the cube in a particular center orbit at random. Each sticker, individually, has a 1/6 chance to land on the like colored face and thus be solved.

I know this is flawed, but I think it at least functions as a basic level estimate, though I don't know if it is an upper bound or a lower bound. From my personal experience having 4 centers solved in 1 center orbit on a 5x5x5 is fairly common, and I think it's a decent enough approximation to the true expected value.

Tangents aside, I am fascinated by how many actual center states there are for a 4x4x4 without overcounting. Are there combinatorial arguments we can use here to calculate this succinctly without a computer, or does this situation probably require a computer to help?

Chris


----------



## Stefan (May 22, 2008)

Chris, you surprise me.
(Yes, that's a hint.)

Oh and after assuming an independent 1/6 chance of each center to be right, why don't you just say 24/6=4?


----------



## cmhardw (May 22, 2008)

Lucas Garron said:


> Anyhow, who else wants to see a robot go down/right/away/dimension-4-positive-wardly/dimension-5-negative-wardly/dimension-6-left-wardly inside a 4x4x4x4x4x4 hypergrid?
> (Yes, that's a puzzle.)
> (But I'm not telling you which puzzle [it's isomorphic to])



Lucas, am I correct in my thinking here?



Spoiler



Assume I have a j x k x l x m 4 dimensional grid. Using your directions I can list the robot's movements on a sheet of paper that I feed into a robot in the "down/right/away/dimension-4-positive-wardly" sense. I have to give the robot (j+k+l+m-4) directions, of 4 different possible types. I can set it up as anagrams of a string of D's for down R's for right A's for away and 4's for fourth-dimensional movement. This gives:

(j+k+l+m-4)!/[(j-1)!*(k-1)!*(l-1)!*(m-1)!] similar to the previous example with a 2D grid. A 5D grid would be very similarly setup this way if it's correct.



As to which puzzle this is isomorphic to I have no idea ;-)

Chris


----------



## Stefan (May 22, 2008)

Hahahahaha.


----------



## ch_ts (May 22, 2008)

24!/(4!)^6 revenge center states

Or C(24,4)*C(20,4)*C(16,4)*C(12,4)*C(8,4)*C(4,4)

Divide by 24 to ignore the cube orientation.


----------



## cmhardw (May 22, 2008)

ch_ts said:


> 24!/(4!)^6 revenge center states
> 
> Or C(24,4)*C(20,4)*C(16,4)*C(12,4)*C(8,4)*C(4,4)
> 
> Divide by 24 to ignore the cube orientation.



What about this particular center state, it does not have 24 possible rotations.

The U and D centers are solved. The F, R, B, L centers are in a checker pattern such that a y2 rotation makes the cube look exactly the same again.

By dividing the (24!)/(4!)^6 term by 24 you are assuming that every single position has been overcounted by a factor of 24. This is not true, and I give the above described position as a counter-example, with only 12 possible rotations due to a high symmetry.

I contest that (24!)/(4!)^6 / 24 = (23)!/(4!)^6 is the correct count for the above reason.

Chris


----------



## Stefan (May 22, 2008)

Some states stay the same with some rotations, so plain division by 24 isn't quite right. But I didn't ask for the number ignoring cube orientation anyway, and your formula correctly computes the number of revenge center states. Then again, I didn't ask for that, either (yes, this is another hint).


----------



## ch_ts (May 22, 2008)

Yeah, you guys are right. I gotta think some more


----------



## Lucas Garron (May 22, 2008)

Chris.:You weren't supposed to solve that, you were supposed to realize what Stefan realized.  (Good solution, though.)

Anyhow, centers are fun. Remember this?

I'll might get to the AAF center states when I get home. Do we agree that no order-3 symmetries are pertinent, as we are not counting color-neutral?


----------



## Mike Hughey (May 22, 2008)

cmhardw said:


> If you sum this expression from n=0 to n=9 you get a cumulative probability of approximately 99%, so most of the time you will have 9 or fewer centers solved (allowing for maybe none solved).



Being an engineer and not a scientist, I'm mostly glossing over the math here (with some interest, but not carefully following it), but the engineer in me is more interested in real-world cases. And this week's second 5x5x5 BLD scramble is a fascinating case - 9 centers solved for each orbit (18 centers solved total)! (By the way, I missed my personal best by just 9 seconds.) I applied the scramble a second time after my solve just to make sure I didn't apply the scramble wrong, and then inverted it and got the solved cube, so I'm pretty sure I scrambled it right.


----------

