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

One thought on “Math Olympiad (Primary Schools) 一筐鸡蛋

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s