Download high-quality eBooks. Instant access, affordable prices, and detailed step-by-step solutions. Perfect for students and professionals
Home » Rabia (page 29)

Rabia

The Birthday Paradox

In a group of 23 people, what is the probability that at least two people share the same birthday?

Answer: Surprisingly, the probability is about 50.7%. This is counterintuitive because we think of 365 days, but the number of possible pairs increases rapidly as people are added to the group, leading to a high likelihood of a shared birthday.

The Tower of Hanoi

You have three rods and n disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top. The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

  1. Only one disk can be moved at a time.
  2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
  3. No disk may be placed on top of a smaller disk.

How do you move the stack of disks?

Answer: The minimum number of moves required is 2n−12^n – 1. The strategy is to move the top n−1n-1 disks to an auxiliary rod, move the nthn^{th} (largest) disk directly to the target rod, then move the n−1n-1 disks from the auxiliary rod to the target rod. The recursive solution involves moving the top n−1n-1 disks, moving the nthn^{th} disk, then moving the n−1n-1 disks again.

The Bridges of Königsberg

The city of Königsberg (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands connected to each other and the mainland by seven bridges. The problem is to find a walk through the city that would cross each bridge once and only once.

Answer: It is not possible to cross each bridge exactly once. This problem led to the development of graph theory, where Euler proved that such a walk is possible if and only if there are zero or two vertices of odd degree. In Königsberg, all vertices have an odd degree.

The Monty Hall Problem

You’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say Door 1, and the host, who knows what’s behind the doors, opens another door, say Door 3, which has a goat. He then asks you if you want to switch to Door 2. Is it to your advantage to switch your choice?

Answer: Yes, it is to your advantage to switch. When you first choose a door, you have a 1/3 chance of picking the car. The host will always reveal a goat behind one of the remaining two doors. By switching, you actually have a 2/3 chance of winning the car, as opposed to sticking with your initial choice, which remains a 1/3 chance.