# A simple problem for some, complicated for me..

Posted 5 months ago
791 Views
|
5 Replies
|
1 Total Likes
|
 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, Answer
5 Replies
Sort By:
Posted 5 months ago Answer
Posted 5 months ago
 permutations and combinationsthey 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 confusedthis 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). Answer
Posted 5 months 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)) Answer
Posted 5 months 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!-2We 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! Answer
Posted 5 months 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. Answer