1. MC math lesson brainstorming

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 :

Stanford Math Circle 7-8 grade Counting November 2022 2 13 Eight people are in a room. One or more of them get an ice-cream cone. One or more of them get a chocolate-chip cookie. In how many different ways can this happen, given that at least one person gets both an ice-cream cone and a chocolate-chip cookie? 14 How many strictly increasing sequences of positive integers begin with 1 and end with 1000? 15 Ten dogs encounter 8 biscuits. Dogs do not share biscuits! How many different ways can the biscuits can be consumed (a) if we assume that the dogs are distinguishable, but the biscuits are not; (b) if we assume that the dogs and the biscuits are distinguishable (for example, each biscuit is a different flavor). (c) if we assume that neither the dogs nor the biscuits are distinguishable? (We are able to distin- guish dogs from biscuits, however. The answer is not 1!) 16 There are 10 adjacent parking spaces in the parking lot. When you arrive in your new Rolls Royce, there are already seven cars in the lot. What is the probability that you can find two adjacent unocupied spaces for your Rolls? Generalize. 17 How many ways can you tile a 3 ⇥ n rectangle with 2 ⇥ 1 dominoes? 18 How many subsets of the set { 1 , 2 , 3 , 4 ,..., 30 } have the property that the sum of the elements of the subset is greater than 232? 19 Prove that for all positive integers n , 1 · ✓ n 1 ◆ + 2 · ✓ n 2 ◆ + ··· + n · ✓ n n ◆ = n 2 n - 1 . 20 Find the number of subsets of { 1 , 2 ,..., n } that contain no two consecutive elements of { 1 , 2 ,..., n } . 21 How many five-card hands from a standard deck of cards contain at least one card in each suit? 22 Four young couples are sitting in a row. In how many ways can we seat them so that no person sits next to their "significant other?" 23 Chicken Nugget Problem . You can buy chicken nuggets only in boxes of a or b nuggets, where a and b are relatively prime (share no prime factors). Call the integer N "edible" if it is possible to buy a meal of exactly N nuggets. Prove that every N ≥ ( a - 1 )( b - 1 ) is edible, and that of the non-negative integers less than or equal to ( a - 1 )( b - 1 ) , exactly half are edible. 24 For any set, prove that the number of its subsets with an even number of elements is equal to the number of subsets with an odd number of elements. For example, the set { a , b , c } in the problem above has 4 subsets with an even number of elements (the empty set has 0 elements, which is even), and 4 with an odd number of elements. 25 Find a nice formula for the sum ✓ n 0 ◆ 2 + ✓ n 1 ◆ 2 + ✓ n 2 ◆ 2 + ··· + ✓ n n ◆ 2 . Can you explain why your formula is true? 8

Stanford Math Circle 7-8 grade Counting November 2022 3 26 Let S be a set with n elements. In how many different ways can one select two not necessarily distinct subsets of S so that the union of the two subsets is S ? The order of selection does not matter; for example, the pair of subsets { a , c } , { b , c , d , e , f } represents the same selection as the pair { b , c , d , e , f } , { a , c } . 27 (USAMO 72) A random number generator randomly generates the integers 1 , 2 ,..., 9 with equal probability. Find the probability that after n numbers are generated, the product is a multiple of 10. 28 Let a 1 , a 2 ,..., a n be an ordered sequence of n distinct objects. A derangement of this sequence is a permutation that leaves no object in its original place. For example, if the original sequence is 1 , 2 , 3 , 4, then 2 , 4 , 3 , 1 is not a derangement, but 2 , 1 , 4 , 3 is. Let D n denote the number of an n -element sequence. Show that D n = n ! ✓ 1 - 1 1! + 1 2! - ··· +( - 1 ) n 1 n ! ◆ . 29 How many nonnegative integer solutions are there to a + b + c + d = 17, provided that d  12? 30 Use a combinatorial argument to show that for all positive integers n , m , k with n and m greater than or equal to k , k  j = 0 ✓ n j ◆✓ m k - j ◆ = ✓ n + m k ◆ . This is known as the Vandermonde Convolution Formula . 31 Decide whether there exist 10,000 ten-digit numbers divisible by seven, all of which can be obtained from one another by a reordering of their digits. 7. 11.13=1001 0000000*05 → 1000000005 2334509881