# 1. MC math lesson brainstorming

.pdf
Stanford Math Circle November 2022 Counting Paul Zeitz, University of San Francisco, [email protected]. Problems for beginners; exercises for the experienced 1 An n -bit string is n -digit "word," each digit of which is either 0 or 1. How many n -bit strings contain at least 1 zero? 2 Imagine a piece of graph paper. Starting at the origin draw a path to the point ( 10 , 10 ) , that stays on the grid lines (which are one unit apart) and has a total length of 20. For example, one path is to go from ( 0 , 0 ) to ( 0 , 7 ) to ( 4 , 7 ) to ( 4 , 10 ) to ( 10 , 10 ) . Another path goes from ( 0 , 0 ) to ( 10 , 0 ) to ( 10 , 10 ) . How many possible different paths are there? 3 Define a domino to be a 1 2 rectangle. In how many ways can a n 2 rectangle be tiled by dominos? 4 In how many ways can two squares be selected from an 8-by-8 chessboard so that they are not in the same row or the same column? 5 Suppose we have three different toys and we want to give them away to two girls and one boy (one toy per child). The children will be selected from 4 boys and 6 girls. In how many ways can this be done? 6 Suppose again that we have three different toys and we want to give them away (one toy per kid) to three children selected from a pool of 4 boys and 6 girls, but now we require that at least two boys get a toy. In how many ways can this be done? 7 How many different ordered triples ( a , b , c ) of non-negative integers are there such that a + b + c = 50? What if the three integers had to be positive? 8 How many ways can the positive integer n can be written as an ordered sum of at least one positive integer? For example, 4 = 1 + 3 = 3 + 1 = 2 + 2 = 1 + 1 + 2 = 1 + 2 + 1 = 2 + 1 + 1 = 1 + 1 + 1 + 1 , so when n = 4, there are 8 such ordered partitions . 9 Ten children order ice cream cones at a store featuring 31 flavors. How many orders are possible in which at least two children get the same flavor? 10 In how many ways can four squares, not all in the same row or column, be selected from an 8-by-8 chessboard to form a rectangle? 11 In how many ways can we place r red balls and w white balls in n boxes so that each box contains at least one ball of each color? 12 Given n points arranged around a circle and the chords connecting each pair of points is drawn. If no three chords meet in a point, how many points of intersection are there? For example, when n = 6, there are 15 intersections. Mr O O :