Discussion Challenge Rules: The class will be divided into 6 groups of around 5 people each. At the beginning of every discussion 3 groups will be randomly assigned to turn in a written proof of the challenge problem and 3 groups will be randomly assigned to present an oral proof of the problem. The speaker will be randomly selected from the group! The grade will be pass/fail on each challenge. You MUST prepare with your group!

• Discussion 1, Feb. 12, 2015 Prove the pigeonhole principle (simple version): If you have \(n\) objects (for instance, 10 pigeons) and \(k \lt n\) containers which hold the objects (for instance, 9 pigeonholes) then at least one container holds 2 or more objects.
• Discussion 2, Feb. 19, 2015 Prove that \(\sqrt{5}\) is irrational.
• Discussion 3, Feb. 26, 2015 You are hosting a party. At some point people start to shake hands with each other (never the same pair twice, nor with oneself). Prove that at least two people have shaken hands with the same number of people.
• Discussion 4, Mar. 5 12, 2015 Prove that there are arbitrarily long sequences of consecutive integers that contain no primes.

  Put a different way, pick a natural number \(k\), there exist \(k\) consecutive integers none of which is a prime number. Example: 24, 25, 26, 27, 28 is the first sequence of length 5 containing no prime numbers.

• Discussion 5, Mar. 19th There are \(n\) non-parallel lines on a plane, no three of which intersect at the same point. How many regions are formed by the line? Prove it.
• Discussion 6, Mar. 26th Prove that \( | \mathcal{P}(A) | = 2^{| A |} \), for any finite set \(A\).
• Discussion 7, Apr. 9th Prove that \( | \mathbb{Z} | = | \mathbb{Q} | \lt | \mathbb{R} | \).
• Discussion 8, Apr. 16th

  Prove that, for any natural \(k \geq 2\) there are at most 2 \(k\)-digit integers that match their square on the \(k\) least significant digits.

  For example when \(k = 2\) we have 25 (625 matches 25) and 76 (5776 matches 76) and no others.

  For super clarity I'll rephrase the question. Let \(S_k = \{ x \mid x \in \mathbb{N}, x \lt 10^k, x \geq 10^{k-1}, x^2 \equiv x \mod{ 10^k } \}\). Prove that \(|S_k| \leq 2\) for natural \(k \geq 2\).

• Discussion 9, April 23rd

  An enthusiastic Texas Hold 'em player selects a different number of decks to combine every time she hosts a tournament. Your challenge is to calculate the number of 7 card hands from \(n\) standard decks of cards which are ranked as a Full House. To clarify, no higher rank is accepted as a Full House.

  A standard deck of cards has 4 suits (Hearts, Clubs, Spades, Diamonds) of 13 ranks each (A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K). The \(n\) decks are identical. A Full House is a five card combination containing 3 cards of one rank and 2 cards of a different rank, for instance (K, K, K, 3, 3). A seven card hand which is ranked as a full house will have five cards that rank as a full house and no other five card subset which would former a better hand. In this particular case the only better hands would be 4 of a kind, 5 of a kind, 6 of a kind, 7 of a kind (flushes and straights are not possible in the same hand as a full house). A hand with 3 of one rank and 3 of a different rank would still qualify as a full house.

  Poker hand rankings

• Discussion 10, April 30th

  You are given a super-powerful "Travelling Salesman Oracle" function, \(TSP\) which takes in a weighted complete graph \(G'\) and a cutoff cost \(c\) then returns a \(0\) or \(1\). The function quickly and accurately returns a \(0\) if there is no circuit of cost \(\leq c\) and \(1\) if there is such a circuit (details below). Your job is to use that oracle to power a circuit detection process on an unweighted graph. That is, given \(G\) an unweighted graph, can you use the oracle and your imagination to return a \(0\) when there is no cycle/loop that visits each vertex exactly once and \(1\) when there is a cycle that visits each vertex once.

  Some details: a circuit is a closed path in a graph. The cost of a circuit is the sum of the edge-weights in the circuit. You are free to create a weighted \(G'\) and cost \(c\) so that \(TSP\) will do the work for you. This process is called a reduction from one problem to another.

  TSP

• Discussion 11, May 7th

  How many ways can a Chutes and Ladders player win in 7 or 8 moves/rolls/flicks? (Each "way" can be thought of as a sequence of die results so roll a 2 then roll a 3 is distinct from roll 3 then roll 2.)

  Chutes and ladders is an old-school boardgame with zero decisions. You start off-board, get a random number 1-6, move that many spaces. If you end at the top of a slide/snake/chute then you slide to the other end, if you end at the bottom of a ladder then you climb to the top of the ladder. (The oldest versions of this game were intended to teach children about Karma...) You win if you end your turn exactly on space 100 (overshooting does not count). Rules are at this link.

  

• Final Discussion, May 15th (I hope you have grown through these problems)

  Please visit this sage cloud starter file. Your goal is to solve randomly generated sock dye puzzles. I have given you a puzzle generator, a dye performer, lots of comments, and a sample solution. Generate a list of colors which, when move are done in that order will solve the problem. A pertinent research paper on super sequences.