Sample math problems

February 25, 2010

<h2>Tiling:</h2>A domino is formed by putting two squares next to each other.<separator></separator>A bent triomino is formed by removing one square from a two by two checker board.<separator></separator>Warm-up: <separator></separator>For which numbers n is it possible to tile an n by n checker board with dominos, that is, to cover it completely with dominos so that no two of them overlap? What if two opposite corners of the board have been removed?<separator></separator>Next consider a 2^n by 2^n checker board for any integer n. Demonstrate that if a single square, no matter which one, is removed from the board, then it is possible to tile the rest with bent triominos.<separator></separator>Hint: <separator></separator>If n=1, then one bent triomino clearly does the job. If n is any integer larger than 1, let m=n-1, and think of the 2^n by 2^n board as made up of four 2^m by 2^m boards. We argue that if we know how to solve the problem for each of the smaller boards, then we also can solve the problem for the larger board: A key idea is to place one bent triomino near the center so that it covers exactly one square in each of the three smaller boards which do not contain the removed square.<separator></separator>Extensions:<separator></separator>For which board sizes whose edges are not necessarily powers of 2 can one do the same? What is possible with rectangular boards that are not square?<separator></separator>Background: <separator></separator>The kind of reasoning employed here is an example of "proof by induction", one of basic tools to tackle infinity and infinitely many different possible cases.<separator></separator> <separator></separator><h2>Ramsey numbers:</h2>How many people must be invited to a party so that there are at least 3 guests all of whom know each other, or at least 3 guests all of whom do not know each other. (People can do this with some coaxing, reall only encouragement is needed.)<separator></separator>Hint:<separator></separator>Suppose Paul is one of six guests at a party and and he knows three of the other guests: Julia, Omayra, and Glenn. Either no two of these there know each other, or at least one pair knows each other and both also know Glenn. A symmetric argument applies when there are three guests none of whom Paul knows.<separator></separator>On the other hand if there are only five guests it is possible that every guest knows exactly two of the others. This is nicely visualized by drawing a complete graph on five vertices -- a graph with five vertices so that every vertex is connected to every other one by an edge. Now try to "color" the edges red or blue (corresponding to knowing and not knowing) so that at each vertex exactly two red and two blue edges meet.<separator></separator>The answer is written as R(3,3)=6 and known as Ramsey number.<separator></separator>The problem with three replaced by four is much harder, but the answer R(4,4) is known. However, the famous Hungarian mathematician Paul Erdös had this to say about R(5,5) and R(6,6):<separator></separator>"Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack." (<a href="http://en.wikiquote.org/wiki/Paul_Erd%C5%91s">http://en.wikiquote.org/w…;)<separator></separator>To read more about Ramsey numbers start here: <a href="http://mathworld.wolfram.com/RamseyNumber.html">http://mathworld.wolfra…;