[psyang]

Originally Posted by psyang

Ah, no response on the number theory problem again. Here's a hint:

Spoiler!

Start looking at the set of all numbers with only 1s as digits: {1, 11, 111, ...}

Also start working with mods.

Ok, no takers. I leave on a little camping trip, so I'll post the solution and a new problem.

solution:

Spoiler!

We are given number n. Want to show that m exists such that m*n consists only of 1s and 0s (in base 10).

Look at set of all numbers with only 1s as digits: {1, 11, 111, ...}

Because the set is infinite, there must exist 2 distinct numbers a and b in the set such that

a mod n = b mod n

Assume a > b

=> a-b = 0 mod n
=> (a-b) is a multiple of n (ie. (a-b)=m*n)

But since a and b consist only of 1s
=>(a-b) consists only of 1s and 0s.

QED