f(a1 + a22) 2a1f(x1) + af(x). (a) Prove by induction that if a, 20 and a...

 

Transcribed Image Text:

f(a1 + a22) 2a1f(x1) + a₂f(x₂). (a) Prove by induction that if a, 20 and a₁ ++ a = 1, then f(a1 + a222 ++anan) 2a₁f(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<a<1 is the fractional part. The rounding operation {a} is defined as follows. If a ≥ 1/2, {x}=k+1, and if a < 1/2, {x}=k. Note that 1/2 is rounded up. For n ≥ 1, a problem from an old Russian mathematics olympiad asks to compute f(a1 + a22) 2a1f(x1) + a₂f(x₂). (a) Prove by induction that if a, 20 and a₁ ++ a = 1, then f(a1 + a222 ++anan) 2a₁f(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<a<1 is the fractional part. The rounding operation {a} is defined as follows. If a ≥ 1/2, {x}=k+1, and if a < 1/2, {x}=k. Note that 1/2 is rounded up. For n ≥ 1, a problem from an old Russian mathematics olympiad asks to compute

Answer rating: 100% (QA)

Here is my solution to Malik MagdunamDiscrexs problem a For n 1 the statement is true If a1 0 then fa1 0 For n 1 assume the statement is true for n We want to show that it is also true for n 1 We have ... View the full answer