BMO 2004 Qusetion3

I am going over some BMO papers recently and not too sure about the answer of this question:

Find the number of the subsets of the set { 1,2,3,4,5,6,7,8,9,10} that contains no three consecutive integers.
We count empty set as one.

Scroll to see replies

Reply 1

sebbie

that is actually question 4 of the 2003 paper.... not sure of a full proof for an answer tho

its 504 (in white)

not sure how to get that though, just looked the answer up...

i'd worked it out as if the subsets could only be of 3 positive integers, thought it seemed easy lol

Reply 2

pure6gapper

where do I possibly get the access to answers for BMO papers?
have done quite a few questions but not so sure about a lot of them .....desperate for an answer sheet

Reply 3

Neapolitan

Let u(n) be the number of subsets of

{1,2,3,...,n}

WITH three consecutive numbers in them, and let S(n) be the collection of all such subsets.

Now a subset of {1,...,n} can be in S(n) by:

(i) being in S(n-1),
(ii) being a subset of S(n-1) with n now added,
(iii) having n-2, n-1, n in it, but not having n-3 and not having a consecutive triple in 1,...,n-4.

Putting this as a recursive relation we see

u(n) = u(n-1) + u(n-1) + [2^(n-4) - u(n-4)]

That is

u(n) = 2u(n-1) - u(n-4) + 2^(n-4)

Hence

u(1)=0,
u(2)=0,
u(3)=1,
u(4) = 3,
u(5) = 2 x 3 - 0 + 2 = 8,
u(6) = 2 x 8 - 0 + 4 = 20,
u(7) = 2 x 20 - 1 + 8 = 47,
u(8) = 2 x 47 - 3 + 16 = 107,
u(9) = 2 x 107 - 8 + 32 = 238,
u(10) = 2 x 238 - 20 + 64 = 520.

The subsets we are looking for are those without a consecutive triple, i.e. 2^n - u(n), or in the case when n=10,

1024 - 520 = 504

Reply 4

dvs

Another way is to see that the number of subsets S(n) of {1,2,...,n} WITHOUT three consecutive elements is given by the relation
S(n) = S(n-1) + S(n-2) + S(n-3)

S(1) = 2^1 = 2
S(2) = 2^2 = 4
S(3) = 2^3 - 1 = 7
S(4) = 13
S(5) = 24
S(6) = 44
S(7) = 81
S(8) = 149
S(9) = 274
S(10) = 504

Reply 5

Neapolitan

Much neater :smile:

EDIT: why does that work? I'm trying to think of the partition you've used.

EDIT2: nevermind, got it.

Reply 6

pure6gapper

That's ingenious but i dont get why it works. Do you mind explaining it further?

Reply 7

dvs

If you look at { 1, 2, ..., n } then S(n-1), S(n-2) and S(n-3) will give you (respectively) the subsets that do not include n, n-1 and n-2 (but the last one includes n and n-1!). Hence adding up their values you, you get all the subsets of n.

Reply 8

KAISER_MOLE

Does S(n) = 2 . S(n-1) + S(n-4) as well? - This is what I came up with for that.

Consider [ a , b , ....n ] with an arbitrary amount of letters in the middle (not conforming to alphabet finite limits like! )

The number of subsets without 3 consective integers contains S(n-1) , as S(n-1) is a subset of S(n) , so all subsets of S(n-1) are included. Also, some of the subsets of S(n-1) can also include n and not have 3 consecutive integers, so we add S(n-1) again, but consider taking off those subsets of S(n-1) that do have 3 consecutive integers, namely n, n-1 and n-2. Those subsets which have 3 consecutive integers elsewhere in the sequence are not in S(n-1) and so can be ignored ...this means that This set of subsets which we are taking away can not contain n-3 at any point....so we are looking for a set of subsets that have no three consecutive integers and contain n-1 and n-2 ...this is accomplished by considering S(n-4) , and adding n-1 and n-2 to the subsets of S(n-4) , which retains the same amount of subsets, having value S(n-4) ....so we subtract this.

This works for all n > 4 , for n < 4 , we can calculate S(n) ...we can use the recurrence relationship to find S(10)

Reply 9

dvs

Do your S(n)s represent my ones or Neapolitan's?

edit: ahh.. obviously Neapolitan's.

edit2: erm.. I'm confused. :redface:

Reply 10

Neapolitan

dvs

Do your S(n)s represent my ones or Neapolitan's?

They - I think - represent the complement of mine, and so his recursion relation is right. You can get it from my recursion by subbing

u(n) = 2^n - s(n)

Reply 11

dvs

Neapolitan

They - I think - represent the complement of mine, and so his recursion relation is right. You can get it from my recursion by subbing

u(n) = 2^n - s(n)

Oh. Yeah, makes sense now. :smile:

Reply 12

pure6gapper

thanks guys. I got it now.

There is another one I want to check the answer.
p, q , r are 3 prime numbers. p divides qr-1, q divides rp-1, r divides pq-1.

Determine all possible values of pqr.

Reply 13

pure6gapper

I can only work out the situation when one prime is 2. so that pqr=30
Dont know how to find solutions when p,q,r are all odd.... Anyone can help me on it?

Reply 14

KAISER_MOLE

pure6gapper

thanks guys. I got it now.

There is another one I want to check the answer.
p, q , r are 3 prime numbers. p divides qr-1, q divides rp-1, r divides pq-1.

Determine all possible values of pqr.

so we have
(qr-1) / p
(rp-1) / q
(pq-1) / r

All as integers, therefore;

(qr-1)(rp-1)(pq-1)/pqr

Is also an integer

= q²r²p² - pq²r - rp²q -pr²q + qr + rp + pq -1 /pqr

The first four terms of the numerator are divisible by pqr to give an integer, so;

(qr + rp + pq - 1 )/pqr = 1/p + 1/q + 1/r - 1/pqr [T]

is also an integer

Thinking about qr-1 / p = qr/p - 1/p being integral

We can tell that p≠q or r, as that would make qr/p integral, and 1/p is not integral since p>1, so it would mean qr-1 / p is not integral, a contradiction.

Using the two other fractions we can determine that p q and r are all distinct.

If none of p q or r =2, maximum of first three terms of [T] is less than 1, so all of [T] is less than 1 because 1/pqr is positive...so one of pqr =2

if none of p,q,r = 3, maximum of first three terms of [T] = 1/2 + 1/5 + 1/7 ≈ 0.84 <1 , so one of pqr = 3

if none of pqr = 5, maximum of first three terms of [T] = 5/6 + 1/7 < (5/6 + 1/6 =1) so one of p, q r = 5

So we have p q and r have to equal 2, 3 and 5 for [T] to even reach a value of 1 ...examining shows that these 3 values give [T] = 1, so it works as a solution , and is the only solution, with pqr = 30

Reply 15

BCHL85

pure6gapper

thanks guys. I got it now.

There is another one I want to check the answer.
p, q , r are 3 prime numbers. p divides qr-1, q divides rp-1, r divides pq-1.

Determine all possible values of pqr.

I consider 2 cases:

If q, q and r are distinct prime numbers then assume p < q < r

p|(qr-1), q|(rp-1), r|(pq-1) (|: divide)
=> pqr|(qr-1)(rp-1)(pq-1) since p, q, r are 3 primes numbers
=> pqr|[(pqr)² - pqr(p+q+r) + pr + rq + qp - 1)
=> pqr|(pr + rq + qp -1)
=> 1/p + 1/q + 1/r - 1/(pqr) = k {k is natural number (≠0)}

Since q < p < r , and they are primes then r >= 5, q >= 3, q >= 2
and pqr > 0
So k < 1/2 + 1/3 + 1/5 - 0 = 31/30
=> k = 1 (since k E N)
and p = 2, q = 3, r = 5
They satisfy k = 1, then they are solutions for that.

--------
If p, q ,r can be equal, then there are 2 cases:
-If p = q = r -> you can see 1/p + 1/q + 1/r = 1 -> k is not in N
-If p = q < r -> you can see p and q can't be greater than 3
So p = q = 2, r > 2, then k = 1 + 1/r - 1/(4r) = 1 + 3/(4r) which is not natural number.
So there no solutions for this case.

Reply 16

dvs

How about this one:
Suppose a and n are natural numbers with the property that there exists an s

\in

N such n divides (a-1)^s. Show that n also divides 1+a+...+a^(n-1).

I haven't been able to make any (significant) progress...

Reply 17

BCHL85

Hmm, let me try :wink:

n divides (a-1)^s, then n must divide (a-1). It's easy to see right?
Then let a - 1 = kn , so a = kn+1, where k E N
Now we have a^n-1 + .... + a² + a¹ + a⁰
= (kn+1)^(n-1) +..... + (kn+1)¹ + (kn+1)⁰
= n*A + (1 + 1 + ... + 1) {n times 1, and A = f(n, k) is a natural number by binomial expansion}
= n*B {B E N}

So n divides a^n-1 + .... + a² + a + 1