Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2000 IMO Problems/Problem 4"

(Added a problem and a solution)
 
m (→‎Solution)
Line 13: Line 13:
 
Consider <math>1</math>, <math>2</math> and <math>3</math>. If they are in different boxes, then <math>4</math> must be in the
 
Consider <math>1</math>, <math>2</math> and <math>3</math>. If they are in different boxes, then <math>4</math> must be in the
 
same box as <math>1</math>, <math>5</math> in the same box as <math>2</math> and so on. This leads to the solution where all
 
same box as <math>1</math>, <math>5</math> in the same box as <math>2</math> and so on. This leads to the solution where all
−
numbers congruent to each other <math>mod 3</math> are in the same box.
+
numbers congruent to each other mod <math>3</math> are in the same box.
  
 
Suppose <math>1</math> and <math>2</math> are in box <math>A</math> and <math>3</math> in box <math>B</math>. Then <math>4</math> must be in box <math>A</math> or <math>B</math>. In
 
Suppose <math>1</math> and <math>2</math> are in box <math>A</math> and <math>3</math> in box <math>B</math>. Then <math>4</math> must be in box <math>A</math> or <math>B</math>. In

Revision as of 05:42, 18 June 2018

Problem

A magician has one hundred cards numbered $1$ to $100$. He puts them into three boxes, a red one, a white one and a blue one, so that each box contains at least one card.

A member of the audience selects two of the three boxes, chooses one card from each and announces the sum of the numbers on the chosen cards. Given this sum, the magician identifies the box from which no card has been chosen.

How many ways are there to put all the cards into the boxes so that this trick always works? (Two ways are considered different if at least one card is put into a different box.)

Solution

Consider $1$, $2$ and $3$. If they are in different boxes, then $4$ must be in the same box as $1$, $5$ in the same box as $2$ and so on. This leads to the solution where all numbers congruent to each other mod $3$ are in the same box.

Suppose $1$ and $2$ are in box $A$ and $3$ in box $B$. Then $4$ must be in box $A$ or $B$. In general, if $k\ge 4$ is in either box $A$ or $B$, then $k + 1$ also must be in box $A$ or $B$. Thus box $C$ is empty which is impossible.

Similarly, it is impossible for $1$ and $3$ to be in box $A$ and $2$ in box $B$.

Thus we are left with the case where $1$ is in box $A$ and $2$ and $3$ in box $B$. Suppose box $B$ contains $2, . . . k$, where $k \ge 3$, but does not contain $k + 1$ and $m$ is the smallest number in box $C$. Then $m > k$.

If $m > k + 1$, then $k + 1$ must be box $A$ and we see that no box can contain $m-1$.

Thus $m = k + 1$. If $k < 99$, we see that no box can contain $k + 2$. Thus $k = 99$. It is easy to see that this distribution works. Thus there altogether $12$ ways - $2$ options times permutation of $3$ colors for each of $3$ boxes.

Taken from: https://sms.math.nus.edu.sg/Simo/IMO_Problems/00.pdf

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2000_IMO_Problems/Problem_4&oldid=95278"