f(a1 + a22) 2a1f(x1) + af(x). (a) Prove by induction that if a, 20 and a ++ a = 1, then f(a1 + a222 ++anan) 2af(21)+ a2f(x2)+...+anf(n). (Evaluating fon a weighted average is at least as large as the weighted average of f.) (b) Show that if f'(x) < 0, then f(x) is concave. Use this to show that log(x) is concave. (c) Prove the AM-GM inequality (see Problem 6.40). [Hint: Take the log.] Problem 6.42. In a line are n disks (black on one side and white on the other). In each step you remove a black disk and flip its neighbors (if they are still there). The goal is to remove all disks. Here is a sample game. 10 0 000 - 0 000-> 0.00 (a) Tinker. Determine when you can win, and when you can't. [Hint: Consider the parity of black disks.] (b) Give an optimal strategy. Prove that your strategy wins all winnable games, and if it fails, the game is not winnable. Problem 6.43. A sliding puzzle is a grid of 9 squares with 8 tiles. The goal is to get the 8 tiles into order (the target configuration). A move slides a tile into empty square. Below we show first a row move, then a column move. 123 066->> (87) Prove that no sequence of moves produces the target configuration. [Hint: The tiles form a sequence going left to right, top to bottom. An inversion is a pair that is out of order. Prove by induction that the number of inversions stays odd.] 4 56 LOSE Problem 6.44. Here is a generalization of Problem 1.43(k). An m x 1 rectangular grid has at least two squares on each side (m, n > 2) and one side is even (so the total number of squares is even). Two squares of opposite colors are removed. Prove by strong induction that the remainder of the board can be tiled by dominos. Problem 6.45. For r R, one can write =k+a where k Z is the integer part and 0