A brain teaser/math problem

[juvan]

Hello all

since I don't know where to post this, I thought this would be the most neutral place to post on this forum. As seen from the title, I have a sort of a brain teaser, although I have to warn, you it's not really good, or fun, and it's completely a math problem (variations, or permutations, never really could tell the difference :P), and it's just something that's been bugging me for a couple of days now.

Firstly I'll just tell you the problem, and then a background of the problem.
Here it goes: We have a 40 letter "word", comprising of two letters, let's say 'r' and 'd', why r and d? I'll tell you later. And we have to use both letters equally, 20 times each, so 20 r's and 20 d's, so there is our 40 letter "word". The question is, how many different "words" can can be created?

Ok this was the problem, now the history behind it. Firstly the problem is from a site projecteuler and I don't want to give any spoilers by accident for people to stumble on, so if this could be a problem, tell me, and we'll stop discussing it.
Now the original problem is actually a bit different, and it goes like this: how many different ways do we have in getting from the top left corner to the bottom right in a 20x20 grid without backtracking. So I was thinking about this, and this is what I came up with so far, kinda modified the problem, maybe simplified it. But this is where I'm stuck now.

So if anybody has any fresh thoughts or ideas, bring it. And what would probably be even better then an outright solution, is maybe some help, or a mental push.

:)

[juvan]

Ooops, promised to tell you why 'r' and 'd', maybe you guessed it, well its just simply 'r' -> Right,
'd' -> Down

[EzwRko23]

40! / (20!)^2

[juvan]

How in the world do you know this??

What are you, a math professor?

[Albatross]

Maybe he just checked the wiki page for combinations, or he took a one-quarter-year course in Discrete Mathematics, or he just copied a solution. More possibilities are possible. What would've been handy is if he explained his solution.

There are (20+20)! ways to arrange 20 rs and 20 ls, however several combinations are indistinguishable from each other, notably there are 20!*20! ways to arrange each r and each l that are indistinguishable from each other (do you see why? There are 20! arrangements for each r if each r were numbered and 20! arrangements for each l if each l were numbered), giving a final solution of 40!/(20!)^2. Bah, that explanation was pathetic.

http://en.wikipedia.org/wiki/Combinatorics

-Albatross

P.S.- I took the class. ^_^

EDIT: 1.4k posts, and counting.

EDIT2: Notice the post below mine. If we can go up and/or left then it gets trickier.

[hamsterman]

I don't really see how the two problems are related. Are you sure 'no backtracking' means that you can't go left or up? That would be a little too simple. I can see no reason why an S shaped path would not be valid.

[chrisname]

Or maybe he's just somewhat capable at maths? I don't think we were debating that he knows (to a certain extent) what he's talking about, it was just that he seems to be trolling. I doubt you'd need a PhD in Mathematics to be able to do that, to be honest.

[hamsterman]

@chisname,
the square is only on 20!

[chrisname]

Ohhhhhhhh. Thought it looked a little outlandish.

[juvan]

Thank you all, good people of the forum, special thanks to Albatross, it worked, the result was correct.

@hamsterman, yes backtracking in this case meant that, you can't go up or left.

@chrisname, that wasn't an actual question, it was a mere momentary astonishment :P, it's just that I've been thinking about it for about 2 hours in my head, and got nowhere.

[chrisname]

To be fair, I couldn't have gotten it on my own regardless of how long I spent on it. My maths is rather poor.

[juvan]

Me neither, though my maths isn't poor, I could probably retire with this problem, having no outside help.

EDIT: pretty cool, found this thing on Pascal's triangle, and as it would seem, this is directly related.

[chrisname]

Well, my maths isn't awful. I can do everything I've been taught (and more, I learned e.g. factorials just because I wanted to know what the n! button was on a calculator and I can sort of grasp limits in Calculus). My mental arithmetic is bad, though. I guess I just need practice.

[EzwRko23]

How in the world do you know this??
What are you, a math professor?

No. A CS assistant professor (well, actually not-yet, but from start of October) :)

@Albatross: do you really believe that someone without math skills would know where to look for in the Wikipedia/book/etc. for the answer? Anyway - it doesn't really count how you come up with the answer, as long as you keep giving correct answers (anyway, this one was easy, and your explanation is not particularly the cleanest one*).

*) A better explanation:
1. Placement of all "r" determines the placement of all "d"s. So now, we have to only consider the placement of "r"s.
2. Let's start putting the "r"s one-by-one into the word. The first "r" can be placed in one of 40 possible positions. The next one in one of the left 39 positions. Then 38, 37 and so on until all r's are left. The last r can be placed in one of the 21 left positions (40 - 19). So we have to calculate: 40*39*38*...*21.
3. All "r"s are identical, so the order of steps (path) in the point 2. does not matter. There are 20 steps in point 2. to get the result. There exist 20! such paths per word (if the set of positions is identical, all the permutation of steps give the same word).
4. So finally:

40*39*...*21 / 20! = 21*...*39*40/20! = 40! / 20! / 20! = 40! / (20!)^2

[jsmith]

juvan, pm me if you want me to explain how I solved the project euler problem (or give you hints).

[z05DSL3A]

xorebxebx wrote:

No. A CS assistant professor (well, actually not-yet, but from start of October) :)

Where?

[Kyon]

Ahh. Combinatorics, my favorite subje- worst subject. Well. It was solved already, anyways. This isn't a hard subject, by the way, it's just that I didn't pay attention to the class.. mainly because our teacher wasn't too enthusiast about this particular part of maths either.

[EzwRko23]

I won't answer this, except saying this is a public university in a city > 1 mln of citizens. Anyway, whatever I write, Albatross would say I copy-pasted it from somewhere. Or that in Internet I can just write whatever I wish. :D

[jsmith]

I think he won't answer because he lied. Nothing about his demeanor that we've seen here befits that of a professor
or assistant professor.

[z05DSL3A]

xorebxebx,

My guess, Warsaw University of Technology and you are about to start a PhD.

Edit: assistant professor might be 'just finished a PhD' in Poland, but anyway still not as grand as it sounds :0)