A. M. Yaglom - Challenging Mathematical Problems With Elementary Solutions, Vol. 1

A. M. Yaglom and I. M. Yaglom

C HALLENGING M ATHEMATICAL P ROBLEMS WITH E LEMENTARY S OLUTIONS

Volume I

Combinatorial Analysis and Probability Theory

Translated by James McCawley, Jr.

Revised and edited by Basil Gordon

DOVER PUBLICATIONS, INC.

NEW YORK

Copyright 1964 by The University of Chicago. All rights reserved.

This Dover edition, first published in 1987, is an unabridged and unaltered republication of the edition published by Holden-Day, Inc., San Francisco, in 1964. It was published then as part of the Survey of Recent East European Mathematical Literature, a project conducted by Alfred L. Putnam and Izaak Wirszup, Dept. of Mathematics, The University of Chicago, under a grant from The National Science Foundation. It is reprinted by special arrangement with Holden-Day, Inc., 4432 Telegraph Ave., Oakland, California 94609.

Originally published as Neelementarnye Zadachi v Ele-mentarnom Izlozhenii by the Government Printing House for Technical-Theoretical Literature, Moscow, 1954.

Library of Congress Cataloging-in-Publication Data

Yaglom, A. M.

[Neelementarnye zadachi v elementarnom izlozhenii. English]

Challenging mathematical problems with elementary solutions / A.M. Yaglom and I.M. Yaglom: translated by James McCawley, Jr.: revised and edited by Basil Gordon.

p. cm.

Translation of: Neelementarnye zadachi v elementarnom izlozhenii. Reprint. Originally: San Francisco: Holden-Day, 1964-1967.

Bibliography: p.

Includes indexes.

Contents: v. 1. Combinatorial analysis and probability theoryv. 2. Problems from various branches of mathematics.

ISBN-13: 978-0-486-65536-9 (pbk.)

ISBN-10: 0-486-65536-9 (pbk.)

1. Combinatorial analysisProblems, exercises, etc. 2. ProbabilitiesProblems, exercises, etc. 3. MathematicsProblems, exercises, etc. I. Yaglom, I. M. (Isaac Moiseevich), 1921- II. Gordon, Basil.

III. Title.

QA 164.11613 1987

511.6dcl9

87-27298

CIP

Manufactured in the United States by Courier Corporation

65536909

www.doverpublications.com

PROBLEMS

PREFACE TO THE AMERICAN EDITION

This book is the first of a two-volume translation and adaptation of a well-known Russian problem book entitled Non-Elementary Problems in an Elementary Exposition. The first part of the original, Problems on Combinatorial Analysis and Probability Theory, appears as Volume I, and the second part, Problems from Various Branches of Mathematics, as Volume II. The authors, Akiva and Isaak Yaglom, are twin brothers, prominent both as mathematicians and as expositors, whose many excellent books have been exercising considerable influence on mathematics education in the Soviet Union.

This adaptation is designed for mathematics enthusiasts in the upper grades of high school and the early years of college, for mathematics instructors or teachers and for students in teachers colleges, and for all lovers of the discipline; it can also be used in problem seminars and mathematics clubs. Some of the problems in the book were originally discussed in sections of the School Mathematics Circle (for secondary school students) at Moscow State University; others were given at Moscow Mathematical Olympiads, the mass problem-solving contests held annually for mathematically gifted secondary school students.

The chief aim of the book is to acquaint the reader with a variety of new mathematical facts, ideas, and methods. The form of a problem book has been chosen to stimulate active, creative work on the materials presented.

The first volume contains 100 problems and detailed solutions to them. Although the problems differ greatly in formulation and method of solution, they all deal with a single branch of mathematics: combinatorial analysis. While little or no work on this subject is done in American high schools, no knowledge of mathematics beyond what is imparted in a good high school course is required for this book. The authors have tried to outline the elementary methods of combinatorial analysis with some completeness, however. Occasionally, when needed, additional explanation is given before the statement of a problem.

Thus the majority of the problems in this book and in its companion volume represent questions in higher (non-elementary) mathematics that can be solved with elementary mathematics. Most of the problems in this volume are not too difficult and resemble problems encountered in high school. The last three sections, however, contain some very difficult problems. Before going on to the problems, the reader should consult the Suggestions for Using the Book.

The book was translated by Professor James McCawley, Jr., of the University of Chicago and edited and revised by Professor Basil Gordon of the University of California at Los Angeles.

Problem 85 was sent by the Russian authors for inclusion in the American edition, and appears here for the first time. A number of revisions have been made by the editor:

1. In order to make volume I self-contained, some problems were transferred to volume II. To replace these, problems 1, 3, 12, and 100 were added. Problem 12, in which the principle of inclusion and exclusion is presented, is intended to unify the treatment of several subsequent problems.

2. Some of the problems have been restated in order to illustrate the same ideas with smaller numbers.

3. The introductory remarks to section 1, 2, 6, and 8 have been rewritten so as to explain certain points with which American readers might not be familiar.

4. Adaptation of this book for American use has involved these customary changes: References to Russian money, sports, and so forth have been converted to their American equivalents; some changes in notation have been made, such as the introduction of the notation of set theory where appropriate; some comments dealing with personalities have been deleted; and Russian bibliographical references have been replaced by references to books in English, whenever possible.

The editor wishes to thank Professor E. G. Straus for his helpful suggestions made during the revision of the book. The Survey wishes to express its particular gratitude to Professor Gordon for the valuable improvements he has introduced.

Neelementarnye zadachi v elementarnom izlozhenii, Moscow: Gostekhizdat, 1954.

SUGGESTIONS FOR USING THE BOOK

This book contains one hundred problems. The statements of the problems are given first, followed by a section giving complete solutions. Answers and hints are given at the end of the book. For most of the problems the reader is advised to find a solution by himself. After solving the problem, he should check his answer against the one given in the book. If the answers do not coincide, he should try to find his error; if they do, he should compare his solution with the one given in the solutions section. If he does not succeed in solving the problem alone, he should consult the hints in the back of the book (or the answer, which may also help him to arrive at a correct solution). If this is still no help, he should turn to the solution. It should be emphasized that an attempt at solving the problem is of great value even if it is unsuccessful: it helps the reader to penetrate to the essence of the problem and its difficulties, and thus to understand and to appreciate better the solution presented in the book.

But this is not the best way to proceed in all cases. The book contains many difficult problems, which are marked, according to their difficulty, by one, two, or three asterisks. Problems marked with two or three asterisks are often noteworthy achievements of outstanding mathematicians, and the reader can scarcely be expected to find their solutions entirely on his own. It is advisable, therefore, to turn straight to the hints in the case of the harder problems; even with their help a solution will, as a rule, present considerable difficulties.