Combinatorics/Motivating Examples and Problems

thumb|right|200px|An 8x8 city grid, with one possible path from A to B highlighted. 1. Picture a small town center, where the streets form an 8x8 square grid, as illustrated in the diagram. How many ways are there to travel from one corner (A) of the town center to the opposite corner (B)? 2. On a chessboard, how many ways are there to position 8 rooks in mutually non-attacking positions? 3. At least how many students must there be in a lecture class to assure that the probability of any two students having the same birthday is at least 1/2? 4. Given n letters and n addressed envelopes, in how many ways can the letters be placed in the envelopes so that no letter is in the correct envelope? (The answer is the nearest integer to ). 5. Kirkman's schoolgirl problem: Fifteen schoolgirls walk each day in five groups of three. Arrange the girls walks for a week so that, in that time each pair of girls walks together in a group just once. Ronald Graham Martin Grötschel László Lovász Handbook of Combinatorics 2 1995 The MIT Press Cambridge, MA 0-262-07171-1 (A solution is provided here.) 6. Euler's officers: Thirty six officers are given, belonging to six regiments and holding six ranks. (No two officers have the same rank and regiment, if their ranks matches then their regiments differ and vice versa). Can the officers be paraded in a 6 by 6 array so that in any line of the array each regiment and each rank occurs precisely once. (The answer is no.) G. Tarry Le problème des 36 officiers Comptes rendus de l'Association française pour l'avancement des sciences 29 1 122–123 1900 https://hdl.handle.net/2027/njp.32101076521697?urlappend=%3Bseq=242%3Bownerid=27021597768906376-252 G. Tarry Le problème des 36 officiers Comptes rendus de l'Association française pour l'avancement des sciences 29 2 170–203 1901 https://hdl.handle.net/2027/hvd.32044106224272?urlappend=%3Bseq=182%3Bownerid=27021597765797130-188 7. Ramsey's game: This 2 player game requires drawing 6 points (no 3 of which are in the same line) on a blank sheet of player and then giving the players differently colored pencils. The players now take turns to connect the points by drawing lines joining them. The first player to produce a monochromatic triangle loses. The question is: Can this game ever end in a draw? (The answer is no. See here.) References