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

Posted 2 months ago
492 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,
5 Replies
Sort By:
Posted 2 months ago
Posted 2 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).
Posted 2 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))
 (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.