Math Is Fun Forum

mikau

Member

Registered: 2005-08-22

Posts: 1,504

interesting set proble, is this the simplest solution?

The set S is formed according to the following rules:

1: 2 ∈ S;
2: n ∈ S ⇒ n+5 ∈ S
3: n ∈ S ⇒ 3n ∈ S

Find the largest integer in the set:
{1, 2, ... , 2008} that does not belong to S.

My solution:

observation 1: every element of S is of the form 2*3^n + 5m where m and n are natural numbers.

proof by induction: clearly it holds for 2, as 2 = 2*3^0 + 5(0).  Suppose by induction that it holds for the first k elements, that is each of those elements is of the form 2*3^n + 5m. then any new element obtained by rules (2) and (3) gives
2*3^n + 5(m+1) and
2*3^(n+1) + 5*(3m) respectively, and clearly m+1, n+1, and 3m are natural numbers if n and m are, and the proof is complete.

observation 2:
Each element of the set is therefore of the form, 2*3^n + 5m and so for any element of the set, we may subtract 5 a certain number of times to get a number of the form 2*3^n, (note n may be 0, and we may not need subtract any 5's)

observation 3: any multiple of 5 cannot be an element of this set.

proof: suppose s is a multiple of 5, if s ∈ S, then by observation 2, we may subtract 0 or more 5's until we obtain a term of the form 2*3^n, but subtracting any number of 5's from a multiple of 5, we still get a multiple of 5. But 2*3^n contains no 5 in its prime factorization, and hence cannot be a multiple of 5. A contradiction. Thus any multiple of 5 cannot be in the set.

Therefore, the maximum integer between 0 and 2008 thats not in the set must be 2005 or greater. Now I just show that 2006, 2007 and 2008 are in the set:
2006: multiply 2 by 3, and add 5 four hundred times
2007, add 5 to 2 four hundred one times
2008, multiply 2 by 3, by 3 again, add 5 three hundred ninety eight times.

so it must be 2005.

was that a good way to go about solving this problem? or is there a more intuitive solution? My solution seems a bit convoluted, and i feel like there must be a simpler argument.

Last edited by mikau (2008-09-05 18:31:47)

---

A logarithm is just a misspelled algorithm.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: interesting set proble, is this the simplest solution?

I did it in pretty much the same way as you.
One difference was that I used 2+5n, 6+5n, 18+5n and 54+5n to show that once you get to 54, all non-multiples of 5 would be in S, which meant I didn't need to show 2006, 2007 and 2008 individually.

I can't think of any way to make that solution significantly shorter though.

---

Why did the vector cross the road?
It wanted to be normal.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: interesting set proble, is this the simplest solution?

I'm not certain, but this may be a Chinese remainder theorem problem.  Unfortunately, don't have the time to look at it more than that right now.  Take a look at reducing the number modulo 15.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."