wu :: forums
« wu :: forums - Combinatorics puzzle »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 8:15am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   easy
(Moderators: ThudnBlunder, SMQ, william wu, Icarus, Eigenray, towr, Grimbal)
   Combinatorics puzzle
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Combinatorics puzzle  (Read 7288 times)
zbudde
Newbie
*





   


Posts: 10
Combinatorics puzzle  
« on: Oct 29th, 2012, 4:31pm »
Quote Quote Modify Modify

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!
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Combinatorics puzzle  
« Reply #1 on: Oct 29th, 2012, 11:44pm »
Quote Quote Modify Modify

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.
« Last Edit: Oct 29th, 2012, 11:53pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
zbudde
Newbie
*





   


Posts: 10
Re: Combinatorics puzzle  
« Reply #2 on: Oct 30th, 2012, 9:19am »
Quote Quote Modify Modify

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?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Combinatorics puzzle  
« Reply #3 on: Oct 30th, 2012, 10:03am »
Quote Quote Modify Modify

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.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
zbudde
Newbie
*





   


Posts: 10
Re: Combinatorics puzzle  
« Reply #4 on: Nov 4th, 2012, 2:04pm »
Quote Quote Modify Modify

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.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Combinatorics puzzle  
« Reply #5 on: Nov 4th, 2012, 10:35pm »
Quote Quote Modify Modify

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?
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
zbudde
Newbie
*





   


Posts: 10
Re: Combinatorics puzzle  
« Reply #6 on: Nov 5th, 2012, 4:55am »
Quote Quote Modify Modify

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).
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Combinatorics puzzle  
« Reply #7 on: Nov 5th, 2012, 11:24am »
Quote Quote Modify Modify

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.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
zbudde
Newbie
*





   


Posts: 10
Re: Combinatorics puzzle  
« Reply #8 on: Nov 6th, 2012, 11:37am »
Quote Quote Modify Modify

The code wasn't working for Python, but I think I may have figured it out anyways.
 
Is
hidden:
40
correct?
IP Logged
zbudde
Newbie
*





   


Posts: 10
Re: Combinatorics puzzle  
« Reply #9 on: Nov 6th, 2012, 11:45am »
Quote Quote Modify Modify

Actually, after reworking the problem your way (with the 6x6 grid) instead of me sort of guessing different ways to do it, I got 42.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Combinatorics puzzle  
« Reply #10 on: Nov 6th, 2012, 12:21pm »
Quote Quote Modify Modify

Yup, 42 is what I got as well; and really, what else could it be.
 
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)
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
zbudde
Newbie
*





   


Posts: 10
Re: Combinatorics puzzle  
« Reply #11 on: Nov 6th, 2012, 7:48pm »
Quote Quote Modify Modify

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!!
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: Combinatorics puzzle  
« Reply #12 on: Nov 9th, 2012, 9:04am »
Quote Quote Modify Modify

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.
IP Logged
jollytall
Senior Riddler
****





   


Gender: male
Posts: 585
Re: Combinatorics puzzle  
« Reply #13 on: Nov 11th, 2012, 8:11am »
Quote Quote Modify Modify

=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.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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