Message Boards Message Boards

0
|
4540 Views
|
5 Replies
|
1 Total Likes
View groups...
Share
Share this post:

A simple problem for some, complicated for me..

Posted 5 years ago

Hi everyone,

A checkerboard figure 5 columns and 3 rows. In how many ways can you mark 9 squares on the board so that each column has at least one check box?

If someone can help me please ?

Thank you,

POSTED BY: Jason Benichou
5 Replies
Anonymous User
Anonymous User
Posted 5 years ago

(I did forget to count something in the last step, and I formatted equations wrong, so I'll repeat)

A checkerboard has 5 columns and 3 rows. In how many ways can you mark 9 squares on the board so that each column has at least one check box?

If the board is 5x3, then there are 15 squares and 15! ways to mark them, n(n-1)(n-2)..., which is notated P(n,n)==n!. Now we've counted it all, and need to count what the problem asked "not to be counted", and remove those (by division).

We add a constraint: only 9 are to be chosen at a time, no more no less. This is P(n,r)==n(n-1)(n-2)... where the first r factors are counted (the remaining are replaced by 1's). We have P(15,9).

15*14*13*12*11*10*9*8*7

So far: we counted all. We reduced that by "taking nine at a time" (by dividing 6x5x4x3x2x1 out).

The P(n,r) formula counts "order". ie, {a,b} and {b,a} are counted as two choices not one. It is not asked which order the 9 markings are made in, so to remove duplicates we use the "combination" formula: C(n,r)==P(n,r)/r!

(15*14*13*12*11*10*9*8*7)/9!

So far: we counted all. We reduced it by "taken nine at a time". We removed duplicate counting in P(n,r) we weren't asked to count by dividing those out.

There is (one) more constraint. That each column has at least one check box. Let's count! With 9 checkers we can fill 3 columns, leaving 2 column open, (which is not allowed). If we disallow 1 choice we are assured one column is not empty. If we again disallow 1 more it could go in 3 places that are not allowed (count), so remove 3 choices. (There are other methods to count the number un-allowed arrangements to remove).

(15*14*13*12*11*10*9*8*7)/9!-1-3

* * * - -
* * * - -
* * * - -

We counted all. We reduced it by "taking nine at a time" by dividing. We removed the duplicates (of permutations v. combinations) by dividing. We subtracted off 4 wrong choices (sets) which, by inspection, "forced" the remaining choices to have at least one checker in each column.

Mathematica does not implement P(n,r) and C(n,r) but you can do so easily. Permutations[] in Mathematica is not for doing the kind of counting as seen above because it's library is so large and capable that sometimes small formula are omitted.

POSTED BY: Anonymous User
Posted 5 years ago

Let me see if i have time to "walk" through this.

A checkerboard 5x3. In how many ways can you mark 9 squares on the board so that each column has at least one check box?

"The Fundamental Counting Principle: if A has 5 ways to choose and B 4 ways to choose, there are 5*4 choices." This is not helpful here. There is a list of squares that can be marked only 1 way.

If the board is 5x3, then there are 15 squares and 15! ways to mark them, n(n-1)(n-2)..., which is notated P(n,n)==n!. Now we've counted it all, and need to count what the problem asked "not to be counted", and remove those (by division).

We add a constraint: only 9 are to be chosen at a time, no more no less. This is P(n,r)==n(n-1)(n-2)... where only r factors of the product are done (the remaining are replaced by 1's). We have P(15,9). 151413121110987.

So far: we counted all. We reduced it by "taken eight at a time" (effectively dividing by the rest).

The last formula counts "order". ie, {a,b} and {b,a} are counted as two choices. It is not asked which order the 9 markings are made in. So remove this by using: C(n,r) is used, C(n,r)==P(n,r)/r!, or 151413121110987/8!

So far: we counted all. We reduced it by "taken eight at a time". We removed duplicate counting P(n,r) had left over we don't use.

There is (one) more constraint. That each column has at least one check box. Let's count. With 9 checkers we can fill 3 rows, leaving 2 rows open, which is not allowed. If we disallow 1 choice we are left with one row open. Disallow 1 more choice, and we have placed the checkers and have left any rows open.

151413121110987/8!-2

We counted all. We reduced it by "taken eight at a time" (dividing by 654321). We removed duplicates (of 8 at a time) (by dividing by 87654321). We subtracted just two choices off, forcing the only two wrong choices that could be made to "not be made".

Mathematica does not implement P(n,r) and C(n,r) but you can do so easily. Permutations[] in Mathematica is not for doing the kind of counting we just did.

I will check my math later - i gotta run to eat!

POSTED BY: Updating Name
Anonymous User
Anonymous User
Posted 5 years ago

((it may not be true that's always the best way to count? but for school books it is what they are asking you to do, do it by steps in the way they present it. find all. find what to remove. do these using their prescribed functions))

POSTED BY: Anonymous User
Anonymous User
Anonymous User
Posted 5 years ago

permutations and combinations

they are all "counting problems". you only need the skill of counting (an important skill).

reduce the problem to a 3x3 board, then to 4x4 so that you can learn to count without getting confused

this will be a problem of counting all permutations, and then after, removing the ones counted that were not needed (making it a combinations problem as well).

POSTED BY: Anonymous User
Posted 5 years ago

Some hints that you should probably think hard about:

The first skill you need to develop is guessing what function to look up in the Mathematica help system. Your problem description includes "how many ways can you mark" and that might make you think of the word "Permutations". Can you find that in the help system and see how that might help you with this problem?

That can give you fifteen items, or lots of lists of fifteen items and you probably want to have each of those divided up into groups of three. You might or might not know the word "Partition". Perhaps you can think how that will help you with this problem.

Less likely that you would be able to guess the next word, but "Map" is something that you should definitely learn how to use. In the help system the examples may include lots of # and & and even /@ and those may be more confusing than helpful at this stage. You can figure those out later. For now you can figure out how to define some function like f[x_]:=2*x; and then Map[f, {1,2,4,z}] and see how Map is "going to do f to every item in that list". When you have practiced a bit with Map then you might start thinking how Map might be used to help you with this problem. You are likely to need to use Map more than once to solve this problem.

You might also use functions like Total and Length and perhaps DeleteCases, but there are always a dozen different ways of doing anything in Mathematica and you may use other functions instead.

If you study this carefully and search the help system and try to imagine how these pieces could be used to get closer to your answer then you should find that your skills have improved and the next problem you need to solve will be easier.

I urge you to not let someone just show you the answer. That won't help you nearly as much with your next problem.

Please let us know how much progress you have made.

POSTED BY: Bill Nelson
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract