wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Combinatorics puzzle
        
(Message started by: zbudde on Oct 29th, 2012, 4:31pm)
Title: Combinatorics puzzle
Post by zbudde on Oct 29th, 2012, 4:31pm
I was given this puzzle by a math professor for a school I am transferring to next year, and I can not for the life of me figure it out.

"How many ways can you fill in a 2x5 grid of boxes with the numbers 0,1,2,...,9 so that the numbers increase across rows and down columns?"

An example would be:

0 1 2 3 4
5 6 7 8 9

My best answer at this point is 95, but I'm not sure if it is correct.

Essentially I added up all of the possibilities each square has in relation to the number above/below it and the number of possibilities in relation to the numbers to each side of it.

If anyone could help out, that would be fantastic!
Title: Re: Combinatorics puzzle
Post by towr on Oct 29th, 2012, 11:44pm
It looks to be equivalent to the number of ways in which you can do five moves up and five moves right without going over the diagonal.
(Upper row equivalent to ith move up, and bottom row equivalent to ith move right; i.e. you add 0-9 from the left such that the upper row is always longer or equal to the bottom row.)

It's probably easiest to fill out the number of ways to get to each square in the grid.

step 1 (it's a six by 6 grid, because we have to do 5 moves in each direction, so we're counting crossing from one square to the other.
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[1][ ][ ][ ][ ][ ]
[1][ ][ ][ ][ ][ ]

step 2
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[1][ ][ ][ ][ ][ ]
[1][1][ ][ ][ ][ ]
[1][ ][ ][ ][ ][ ]

step 3
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[1][ ][ ][ ][ ][ ]
[1][2][ ][ ][ ][ ]
[1][1][ ][ ][ ][ ]
[1][ ][ ][ ][ ][ ]

step 4
[ ][ ][ ][ ][ ][ ]
[1][ ][ ][ ][ ][ ]
[1][3][ ][ ][ ][ ]
[1][2][2][ ][ ][ ]
[1][1][ ][ ][ ][ ]
[1][ ][ ][ ][ ][ ]

step 5
[1][ ][ ][ ][ ][ ]
[1][4][ ][ ][ ][ ]
[1][3][5][ ][ ][ ]
[1][2][2][ ][ ][ ]
[1][1][ ][ ][ ][ ]
[1][ ][ ][ ][ ][ ]

And I'll leave the rest to you.

(NB: 95 is a bit on the high side)

As a followup puzzle, try the same with the numbers 0-14 in a 5x3 grid of boxes.
Title: Re: Combinatorics puzzle
Post by zbudde on Oct 30th, 2012, 9:19am
Sorry for posting this in hard, it seemed pretty difficult to me (and its for a 300 level class) lol.

But I am not too sure I follow you. How you were structuring it, the top is larger than the bottom as opposed to vice versa. But even if inverted, it couldn't be right because the first in the top row must always be 0 and the last in the bottom must always be 9. But I suppose that could be an easy fix as well.
If I were to do the problem the way you have would it be basically writing out all of the possibilities? I've already written out about 28 possibilities before my patience ran too thin. There must be an easier way to figure out how many there are without writing them all out. Right?
Title: Re: Combinatorics puzzle
Post by towr on Oct 30th, 2012, 10:03am
Maybe I didn't explain it very well.

In the original problem, when you enter the number 0..9 (in order) in the two rows, at every step you need to have filled in at least as many number in the top row as in the bottom row.

So,
[0][2][3][  ][  ]
[1][  ][  ][  ][  ]
is a valid in-between state

But if at any point you have something like
[0][2][  ][  ][  ]
[1][3][4][  ][  ]
Then it's pretty obvious you can't get a valid filled in grid by continuing.

So this is equivalent to repeatedly picking either top row, or bottom row, where at any step along the way you must have picked the top row at least as often as the bottom row.
Therefore, this is equivalent to moving up and right in a 6x6 grid of squares, starting at the bottom left and ending in the top right, all the while avoiding the lower right triangle (so you have to start by going up, and you can't cross the diagonal).

In that form the puzzle is pretty easy to solve by just filling in in how many way you can get to each square in the 6x6 grid, which is simply a matter of adding the value in the square to the left and the square below (because those are the square you can potentially come from when moving to the right and up).
So that's what I've shown in each step in my previous post, how the 6x6 grid gradually gets filled in. 5 more steps and you can read the number of ways to get to the top right, which is the same as the number of solutions for the original problem.
Title: Re: Combinatorics puzzle
Post by zbudde on Nov 4th, 2012, 2:04pm
Thanks man! Assuming I did it right, I came up with 91 as my answer. I'm wondering if the method I had used was right, but I just made a minor calculation error along the way.
Title: Re: Combinatorics puzzle
Post by towr on Nov 4th, 2012, 10:35pm
The answer I found is not even half that, and I double-checked it by having a computer count the possibilities as well.
How did you get 91?
Title: Re: Combinatorics puzzle
Post by zbudde on Nov 5th, 2012, 4:55am
Well, clearly I did something wrong. Though under 45 seems a bit low. I have already written about 35 or so (I'll check to say how many later today) without even seemingly even coming close to finishing (I stopped because I had written enough to prove one theory wrong, not because I couldn't think of more).
Title: Re: Combinatorics puzzle
Post by towr on Nov 5th, 2012, 11:24am
If you're interested, here is a python script to count the number of valid arrangements

Python
Code:
def permutations(L):
if len(L) <= 1:
 yield L
else:
 a = [L.pop(0)]
 for p in permutations(L):
  for i in range(len(p)+1):
   yield p[:i] + a + p[i:]

def countArrangements():
t = 0;
for perm in permutations(range(10)):
 [a,b,c,d,e,f,g,h,i,j] = perm;
 if a<b<c<d<e and f<g<h<i<j and a<f and b<g and c<h and d<i and e<j:
  t+=1;
print t;

countArrangements()


It tries all possible arrangements for
[ a ][ b ][ c ][ d ][ e ]
[ f ][ g ][ h ][ i ][ j ]
then checks that the number increase across rows and down columns.
Title: Re: Combinatorics puzzle
Post by zbudde on Nov 6th, 2012, 11:37am
The code wasn't working for Python, but I think I may have figured it out anyways.

Is [hideb]40[/hideb] correct?
Title: Re: Combinatorics puzzle
Post by zbudde on Nov 6th, 2012, 11:45am
Actually, after reworking the problem your way (with the 6x6 grid) instead of me sort of guessing different ways to do it, I got [hide]42[/hide].
Title: Re: Combinatorics puzzle
Post by towr on Nov 6th, 2012, 12:21pm
Yup, [hide]42[/hide] is what I got as well; and really, what else could it be (http://en.wikipedia.org/wiki/Phrases_from_The_Hitchhiker%27s_Guide_to_the_Galaxy#Answer_to_the_Ultimate_Question_of_Life.2C_the_Universe.2C_and_Everything_.2842.29).

Strange the python code isn't working for you; maybe you're using a different version? (I used 2.6, it should work for 2.7 as well, but I don't know about 3.x)
Title: Re: Combinatorics puzzle
Post by zbudde on Nov 6th, 2012, 7:48pm
I've got 3.3 I believe. Man... How did I not think of using my nerdiness to recognize that of course that would be the answer!!
Title: Re: Combinatorics puzzle
Post by Grimbal on Nov 9th, 2012, 9:04am
The same question was asked somewhere here for a 3x3 board:  In how many ways can you arrange the numbers 1 to 9 in a 3x3 matrix such that each row and each column is sorted in increasing order.
Title: Re: Combinatorics puzzle
Post by jollytall on Nov 11th, 2012, 8:11am
=2*(5+(2*5+(2*3)))=42. What else again?

The logic on an ABC-123 board:
Top-left (A1) is always #1.
The #2 can go to B1 or A2. Because of symmetry it is enough to check B1. This gives the first "2*("

#3 can go to C1. In this case we are back to a 3x2 matrix, what is 5 options. This gives the "2*(5+"
#3 can also go to A2. This gives the first unnecessary extra brackets.

When #3 is on A2, then #4 can go on either C1, A3 or B2.
C1 and A3 are again symmetrical (hence the next "2*" If #4 is on A3, we are back to the 3x2 matrix (top left corner filled already). This is again 5.
If #4 is on B2, then we get to the second unnecessary bracket. #5 must be on A3 or C1. Because of symmetry agan, this is 2* assuming C1.
Now we only have to count how many numbers (none, #6 or both #6and#7) we put in row 3, before we fill in C2. That is three options.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board