Math Olympiad (Primary Schools) 一筐鸡蛋

One basket of eggs.
1粒1粒拿,正好拿完。
Remove 1 by 1, nothing left in basket.

2粒2粒拿,还剩1粒。
Remove 2 by 2, one left in basket.

3粒3粒拿,正好拿完。
Remove 3 by 3, nothing left in basket.

4粒4粒拿,还剩1粒。
Remove 4 by 4, one left in basket.

5粒5粒拿,还差1粒才能拿完。
Remove 5 by 5, short of one to complete.

6粒6粒拿,还剩3粒。
Remove 6 by 6, 3 left in basket.

7粒7粒拿,正好拿完。
Remove 7 by 7, nothing left in basket.

8粒8粒拿,还剩1粒。
Remove 8 by 8, one left in basket.

9粒9粒拿,正好拿完。
Remove 9 by 9, nothing left in basket.

请问筐里最少有几粒鸡蛋 ?
At least how many eggs are there in the basket?

[Hint] This is a Chinese Remainder Problem (” 韩信点兵”)

—— [Solution] —–

Let there be minimum X eggs in the basket.

Remove 1 by 1, nothing left in basket:
X = 0 mod (1) …[1]
=> trivial & useless !

Remove 2 by 2, one left in basket:
X = 1 mod (2) … [2]

Remove 3 by 3, nothing left in basket:
X = 0 mod (3) … [3]

Remove 4 by 4, one left in basket:
X = 1 mod (4) … [4]

Remove 5 by 5, short of one to complete:
X = -1 mod (5) … [5]

Remove 6 by 6, 3 left in basket:
X = 3 mod (6) … [6]

Remove 7 by 7, nothing left in basket:
X = 0 mod (7) … [7]

Remove 8 by 8, one left in basket:
X = 1 mod (8) … [8]

Remove 9 by 9, nothing left in basket:
X = 0 mod (9) … [9]

Simplify [6] = [3]
X = 3 mod (6)
X = 3 mod (3×2)
X = 3 mod (3)
X = 0 mod (3) … [3]

Notice [3], [7],[9]: X is multiple of 3, 7, 9
=> X is mulitple of LCM (3,7,9) = 63
X = 0 mod (63) … [3,7,9]

Similarly,
X = 1 mod (2)
X = 1 mod (4)
X = 1 mod (8)
=> X = 1 mod (LCM {2, 4, 8}) [Note @]
=> X = 1 mod (8) … [8]

[Note @]:
\forall n,m,t,t',t" \in \mathbb{ N }
X = 1 mod (2)
=> X – 1 = 2n
Similarly,
X = 1 mod (4) <=> X – 1 = 4m
X = 1 mod (8) <=> X – 1 = 8t = 4.(2n)t’ = 2.(4m)t”
These 3 equations <=> X = 1 mod (8)

Simplify the 9 equations by considering only the remaining 3 equations:

X = 0 mod (63) … [3,7,9]
X = -1 mod (5) … [5]
X = 1 mod (8) … [8]

Since (8, 5, 63 ) are co-primes pair-wise – ie (8, 5), (8, 63), (5, 63) are relative primes to each other in each pair – we can apply the Chinese Remainder Theorem to the last 3 equations:

\boxed {X = (63 \times 5).u1 +(63 \times 8).u2 +(5 \times 8).u3 \mod (8 \times 5 \times 63)} …[#]

By sequentially “mod” the equation [#] by 8, 5, 63, we get:

(63×5).u1 = 1 mod (8) … [8]
315.u1 = (39×8+3).u1 = 1 mod (8)
3.u1 = 1 mod (8)
=> u1 = 3 [as 9 = 1 mod (8)]

(63×8).u2 = -1 mod (5)… [5]
504.u2 = (50×11 – 1).u2 = -1 mod (5)
-1.u2= -1 mod (5)
u2 = 1 [as -1 = -1 mod (5)]

(5×8).u3 = 0 mod (63)… [3,7,9]
40.u3 = 0 mod (63)
u3 = 0 [as 0 = 0 mod (63) ]

[#]:
X = (63×5).u1 + (63×8).u2 +(5×8).u3 mod (8x5x63)
X = (63×5).3 + (63×8).1 + (5×8).0 mod (2520)

X = 63 x 23 = 1449 mod (2550)

\boxed {\text{Minimum Eggs } = 1449}

Advertisements

IMO Super-Coach: Rukshin

Rukshin at 15 was a troubled russian kid with drink and violence, then a miracle happened: He fell in love with Math and turned all his creative, aggressive, and competitive energies toward it.

He tried to compete in Math olympiads, but outmatched by peers. Still he believed he knew how to win; he just could not do it himself.

He formed a team of schoolchildren a year younger than he and trained them.
At 19 he became an IMO coach who produced Perelman (Gold IMO & Fields/Clay Poincare Conjecture). In the decades since, his students took 70 IMO, include > 40 Golds.

Rukshin’s thoughts on IMO:

1. IMO is more like a sport. It has its coaches, clubs, practice sessions, competitions.

2. Natural ability is necessary but NOT sufficient for success: The talented kid needs to have the right coach, the right team, the right kind of family support, and, most important, the WILL to win.

3. At the beginning, it is nearly impossible to tell the difference between future (Math) stars and those who will be good (at IMO) but never great (Mathematician).