Book contents
- Frontmatter
- Note to the Reader
- Preface
- Contents
- 1 Transformations and their Iteration
- 2 Arithmetic and Geometric Means
- 3 Isoperimetric Inequality for Triangles
- 4 Isoperimetric Quotient
- 5 Colored Marbles
- 6 Candy for School Children
- 7 Sugar Rather Than Candy
- 8 Checkers on a Circle
- 9 Decreasing Sets of Positive Integers
- 10 Matrix Manipulations
- 11 Nested Triangles
- 12 Morley's Theorem and Napoleon's Theorem
- 13 Complex Numbers in Geometry
- 14 Birth of an IMO Problem
- 15 Barycentric Coordinates
- 16 Douglas-Neumann Theorem
- 17 Lagrange Interpolation
- 18 The Isoperimetric Problem
- 19 Formulas for Iterates
- 20 Convergent Orbits
- 21 Finding Roots by Iteration
- 22 Chebyshev Polynomials
- 23 Sharkovskii's Theorem
- 24 Variation Diminishing Matrices
- 25 Approximation by Bernstein Polynomials
- 26 Properties of Bernstein Polynomials
- 27 Bézier Curves
- 28 Cubic Interpolatory Splines
- 29 Moving Averages
- 30 Approximation of Surfaces
- 31 Properties of Triangular Patches
- 32 Convexity of Patches
- Appendix A Approximation
- Appendix B Limits and Continuity
- Appendix C Convexity
- Bibliography
- Hints and Solutions
- Index
6 - Candy for School Children
- Frontmatter
- Note to the Reader
- Preface
- Contents
- 1 Transformations and their Iteration
- 2 Arithmetic and Geometric Means
- 3 Isoperimetric Inequality for Triangles
- 4 Isoperimetric Quotient
- 5 Colored Marbles
- 6 Candy for School Children
- 7 Sugar Rather Than Candy
- 8 Checkers on a Circle
- 9 Decreasing Sets of Positive Integers
- 10 Matrix Manipulations
- 11 Nested Triangles
- 12 Morley's Theorem and Napoleon's Theorem
- 13 Complex Numbers in Geometry
- 14 Birth of an IMO Problem
- 15 Barycentric Coordinates
- 16 Douglas-Neumann Theorem
- 17 Lagrange Interpolation
- 18 The Isoperimetric Problem
- 19 Formulas for Iterates
- 20 Convergent Orbits
- 21 Finding Roots by Iteration
- 22 Chebyshev Polynomials
- 23 Sharkovskii's Theorem
- 24 Variation Diminishing Matrices
- 25 Approximation by Bernstein Polynomials
- 26 Properties of Bernstein Polynomials
- 27 Bézier Curves
- 28 Cubic Interpolatory Splines
- 29 Moving Averages
- 30 Approximation of Surfaces
- 31 Properties of Triangular Patches
- 32 Convexity of Patches
- Appendix A Approximation
- Appendix B Limits and Continuity
- Appendix C Convexity
- Bibliography
- Hints and Solutions
- Index
Summary
The first problem in this Chapter illustrates again how powerful the strategy of maximum and minimum is in solving problems related to smoothing transformations.
Problem. 1 [BMO 1962]. A number of students sit in a circle while their teacher gives them candy. Each student initially has an even number of pieces of candy. When the teacher blows a whistle, each student simultaneously gives half of his or her own candy to the neighbor on the right. Any student who ends up with an odd number of pieces of candy gets one more piece from the teacher. Show that no matter how many pieces of candy each student has at the beginning, after a finite number of iterations of this transformation all students have the same number of pieces of candy.
Solution. Each distribution of candy is described by an ordered set of nonnegative integers. The transformation just defined carries one ordered set into another. We are required to prove that the transformation possesses a smoothing property.
Initially there is a student who has the greatest number of candies, denoted by 2m, and there is a student who has the smallest number of candies, denoted by 2n. If m = n then all students have the same number of candies, and the transformation preserves this status quo.
Suppose m > n. Three observations can be made about the distribution of candy after the transformation:
1. The number of candies each student has is still between 2n and 2m, inclusive.
- Type
- Chapter
- Information
- Over and Over Again , pp. 26 - 28Publisher: Mathematical Association of AmericaPrint publication year: 1997