Discrete Mathematics – Kenneth Rosens

The Birthday Problem A famous puzzle asks for the smallest number of people needed in a room so that it is more likely than not that at least two of them have the same day of the year as their birthday. Most people find the answer, which we determine in Example 13, to be surprisingly small.

After we solve this famous problem, we will show how similar reasoning can be adapted to solve a question about hashing functions. The Birthday Problem What is the minimum number of people who need to be in a room so that the probability that at least two of them have the same birthday is greater than 1/2? Solution: First, we state some assumptions. We assume that the birthdays of the people in the room are independent.

Furthermore, we assume that each birthday is equally likely and that there are 366 days in the year. (In reality, more people are born on some days of the year than others, such as days nine months after some holidays including New Year’s Eve, and only leap years have 366 days.) To find the probability that at least two of n people in a room have the same birthday, we first calculate the probability pn that these people all have different birthdays.

Then, the probability that at least two people have the same birthday is 1– pn. To compute pn, we consider the birthdays of the n people in some fixed order. Imagine them entering the room one at a time; we will compute the probability that each successive person entering the room has a birthday different from those of the people already in the room.

The birthday of the first person certainly does not match the birthday of someone already in the room. The probability that the birthday of the second person is different from that of the first person is 365/366 because the second person has a different birthday when he or she was born on one of the 365 days of the year other than the day the first person was born. (The assumption that it is equally likely for someone to be born on any of the 366 days of the year enters into this and subsequent steps.)

The probability that the third person has a birthday different from both the birthdays of the first and second people given that these two people have different birthdays is 364/366. In general, the probability that the jth person, with 2 ≤j ≤366, has a birthday different from the 7 / Discrete Probability birthdays of the j −1 people already in the room given that these j −1 people have different birthdays is 366 −( j −1) = 367 −j .

Published by McGraw-Hill, a business unit of The McGraw-Hill Companies, Inc., 1221 Avenue of the Americas, New York, NY 10020. Copyright © 2012 by The McGraw-Hill Companies, Inc. All rights reserved. Previous editions © 2007, 2003, and 1999. No part of this publication may be reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior written consent of The McGraw-Hill Companies, Inc., including, but not limited to, in any network or other electronic storage or transmission, or broadcast for distance learning.

Some ancillaries, including electronic and print components, may not be available to customers outside the United States. This book is printed on acid-free paper. 1 2 3 4 5 6 7 8 9 0 DOW/DOW 1 0 9 8 7 6 5 4 3 2 1 ISBN 978-0-07-338309-5 MHID 0-07-338309-0 Vice President & Editor-in-Chief: Marty Lange Editorial Director: Michael Lange Global Publisher: Raghothaman Srinivasan Executive Editor: Bill Stenquist Development Editors: Lorraine K. Buczek/Rose Kernan Senior Marketing Manager: Curt Reynolds Project Manager: Robin A. Reed Buyer: Sandy Ludovissy Design Coordinator: Brenda A.

Rolwes Cover painting: Jasper Johns, Between the Clock and the Bed, 1981. Oil on Canvas (72 × 126 1/4 inches) Collection of the artist. Photograph by Glenn Stiegelman. Cover Art © Jasper Johns/Licensed by VAGA, New York, NY Cover Designer: Studio Montage, St. Louis, Missouri Lead Photo Research Coordinator: Carrie K.

Burger Media Project Manager: Tammy Juran Production Services/Compositor: RPK Editorial Services/PreTeX, Inc. Typeface: 10.5/12 Times Roman Printer: R.R. Donnelley All credits appearing on this page or at the end of the book are considered to be an extension of the copyright page. Library of Congress Cataloging-in-Publication Data Rosen, Kenneth H. Discrete mathematics and its applications / Kenneth H. Rosen. — 7th ed. p. cm. Includes index. ISBN 0–07–338309–0 1. Mathematics. 2. Computer science—Mathematics. I. Title. QA39.3.R67 2012 511–dc22 2011011060 www.mhhe.com Contents About the Author vi Preface vii The Companion Website xvi To the Student xvii 1 The Foundations: Logic and Proofs .

. . . . . . . . . . . . . . . . . . . . . . . .

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.

Book Information

• Unique ID: e5fc7088731065b0
• File Extension: .pdf
• File Size: 10,143,359 bytes (9.673 MB)
• Title: –
• Author: Unknown
• ISBN: 9780073383095, 9780077353506, 9780077353490, 0073383090, 0077353501, 0077353498, 0110110110, 1111111111, 0000000000
• Pages: 1072
• Language: English (en)

Reading & Word Statistics

• Estimated Reading Time: 3465.76 minutes
• Total Words: 693,153
• Total Characters: 3,572,087
• Average Words per Page: 646.6
• Average Characters per Page: 3332.17

Most Frequent Words

set (2801), number (2391), two (2225), show (1938), one (1839), example (1798), graph (1757), integers (1652), integer (1512), using (1499), use (1458), algorithm (1415), positive (1384), used (1384), true (1362), vertices (1203), first (1182), many (1108), relation (1101), let (1093), elements (1057), vertex (1038), function (988), solution (944), numbers (943), find (906), proof (887), every (884), theorem (883), mod (860), least (842), tree (831), suppose (817), three (811), step (805), section (760), edges (759), sets (750), also (749), bit (747), given (741), exercise (740), statement (740), figure (732), prove (713), element (706), find (690), string (665), sequence (663), different (654), functions (637), list (627), induction (621), problem (621), probability (617), strings (616), graphs (614), real (611), see (605), sum (604), follows (592), path (590), note (588), value (585), terms (580), form (579), computer (570), ways (562), whether (551), state (548), determine (541), edge (540), second (535), mathematical (533), called (529), boolean (520), between (517), length (513), mathematics (509), four (500), simple (499), exercises (496), possible (485), values (484), inductive (478), shown (473), recurrence (464), relations (464), hence (458), algorithms (454), circuit (454), new (452), order (448), input (445), table (442), time (435), definition (434), people (433), prime (428), machine (425).

PDF Download