DeTemple Duane - Solutions Manual to Accompany Combinatorial Reasoning: An Introduction to t

DUANE DeTEMPLE
WILLIAM WEBB

Department of Mathematics
Washington State University
Pullman, WA

Copyright 2014 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.
Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

DeTemple, Duane W.
Solutions manual to accompany combinatorial reasoning : an introduction to the art
of counting / Duane DeTemple, William Webb.
pages cm
ISBN 978-1-118-83078-9 (pbk.)
1. Combinatorial analysisTextbooks. 2. Mathematical analysisTextbooks. I. Webb, William, 1944- II. Title.
QA164.D48 2013
511.6dc23

2013035522

This manual provides the statements and complete solutions to all of the odd numbered problems in the textbook Combinatorial Reasoning: An Introduction to the Art of Counting. The definitions, theorems, figures, and other problems referenced in the solutions contained in this manual are to that book.

The most important thing to remember is that you should not turn to any solution in this manual without first attempting to solve the problem on your own. Many of the problems are subtle or complex and therefore require considerable thoughtand time!before you can expect to find a correct method of solution. You will learn best by trying to solve a problem on your own, even if you are unsuccessful. We hope that most often you will consult this manual simply to confirm your own answer. Often your answer will be the same as ours, but sometimes you may have found a different method of solution that is not only correct, but may even be better than ours (if so, please send us your alternative solution at the address below). If the answer to a problem eludes you even after a good effort, then take a look at the solution offered here. Even in this case, it is best only to read the beginning of the solution and see if you can continue to solve the problem on your own.

Many students wonder how to go about attacking nonroutine problems. We have listed some suggestions below that may be helpful for solving combinatorial problems and more generally for solving problems in any branch of mathematics.

• Try small cases and look for patterns
• Separate a problem into cases
• Draw a figure
• Make a table of values
• Look for a similar or related problem, one you already know how to solve
• For combinatorial problems, apply one of the strategies explored in the textbook: use the addition and multiplication principles; identify the problem as a permutation, combination, or distribution; find and solve a recurrence relation; use a generating function; use the principle of inclusion/exclusion; restate the problem to relate it to a problem answered by well known numbers such as binomial coefficients, Fibonacci numbers, Stirling numbers, partition numbers, Catalan numbers, and so on.

For a more complete discussion of mathematical problem solving, you are encouraged to consult How to Solve It, the classic, but still useful, book of George Plya.

DUANE DETEMPLE

WILLIAM WEBB

Washington State University, Pullman, WA

detemple@wsu.edu and webb@math.wsu.edu

1. 1.2.1 A bag contains 7 blue, 4 red, and 9 green marbles. How many marbles must be drawn from the bag without looking to be sure that we have drawn

   1. a pair of red marbles?
   2. a pair of marbles of the same color?
   3. a pair of marbles with different colors?
   4. three marbles of the same color?
   5. a red, blue, and green marble?

   Answer

   (a) 18 (b) 4 (c) 10 (d) 7 (e) 17

2. 1.2.3. There are 10 people at a dinner party. Show that at least two people have the same number of acquaintances at the party.

   Answer

   Each person can know any where from 0 (no one) to 9 (everyone) people. But if someone knows no one, there cannot be someone who knows everyone, and vice versa. Thus, place the 10 people into the 9 boxes that are labeled 1, 2, , 8, and 0|9. By the pigeonhole principle, some box has at least 2 members. That is, there are at least two people at the party with the same number of acquaintances.

3. 1.2.5 Given any five points in the plane, with no three on the same line, show that there exists a subset of four of the points that form a convex quadrilateral.

   [Hint: Consider the convex hull of the points; that is, consider the convex polygon with vertices at some or all of the given points that encloses all five points. This scenario can be imagined as the figure obtained by bundling the points within a taut rubber band that has been snapped around all five points. There are then three cases to consider, depending on whether the convex hull is a pentagon, a quadrilateral containing the fifth point, or a triangle containing the other two given points.]

   Answer

   If the convex hull is a pentagon, each set of 4 points are the vertices of a convex quadrilateral. If the convex hull is a quadrilateral, the convex hull itself is the sought quadrilateral. If the convex hull is a triangle, the line formed by the two points within the triangle separates the vertices of the triangle into opposite half planes. By the pigeonhole principle, there are two points of the triangle in the same half plane. These two points, together with the two points within the triangle, can be combined to form the desired convex quadrilateral.