All About Math Olympiad Training & Questions

[SKT]

Let S = {1,2,…,4022}. Let T be the subset of S such that no number in T is divisible by another. What is the maximum size of T, i.e. the maximum number of elements that can be in T?


TIA

[FrekiWang]

SKT:

Let S = {1,2,...,4022}. Let T be the subset of S such that no number in T is divisible by another. What is the maximum size of T, i.e. the maximum number of elements that can be in T?

TIA

The answer is 2011, i.e. half of 4022.

A specific example can be T={2012,2013,2014,....,4022} which obviously satisfies the condition.

Now let's prove the maximum size cannot exceed 2011.

Define 2011 subsets of T as follows:

A1={1, 1x2, 1x2x2, 1x2x2x2 ,...., 1x2^11}
(1x2^11=2048, 1x2^12=4096>4022)

A3={3, 3x2, 3x2x2, ...., 3x2^10}

A5={5, 5x2, 5x2x2, ...., 5x2^9}

A7={7, 7x2, 7x2x2, ...., 7x2^9}
....
A2009={2009, 2009x2}

A2011={2011, 2011x2}

A2013={2013}

A2015={2015}
....
A4019={4019}

A4021={4021}

A little explaination here for those who cannot see the pattern,
Subset A(2k-1) (k=1,2...2012) contains all numbers that are equal to (2k-1) multiply by powers of 2 and do not exceed 4022. There are 2011 such subsets in total.

Suppose the maximum size of the subset T exceeds 2011 (i.e. at least 2012) and all elements belong to at least one of the 2011 subsets mentioned above, then according to 'pigeonhole principle', at least 2 or more elements must belong to one of the subsets.

For these 2 elements, the greater number is always divisible by the smaller one, thus it is not possible for a subset S to have a size that exceeds 2011.

PS: the problem can be extended to:

Let S = {1,2,...,2n}. Let T be the subset of S such that no number in T is divisible by another. What is the maximum size of T, i.e. the maximum number of elements that can be in T?

and the answer is n, you can show n+1 is not possible using a similar approach, in fact this is one classical application of 'pigeonhole principle'

[megans113]

Please help me solve this...

Refer to picture for problem....
http://postimage.org/image/49en7e90/

[francbat]

connect the vertex at the top to the intersection of the 2 cevians.

let y be the unknown area to the left, x to the right. using areas we have
x/(8+y) = 1/2 and y/(x+5) = 4/5. solving yields x=10, y =12, so your area is 22.

[FrekiWang]

megans113:

Please help me solve this...

Refer to picture for problem....
http://postimage.org/image/49en7e90/

From what I observe on your paper, you already have the sufficient knowledge to solve the problem, so I will make my solution a simplified version because I think you can understand it.

Join the top vertice to the point of intersection, it divides the region into two, let the area of the left one be A, the other one be B.

For the working you have written on that piece, I think you already understand the significance of the ratio 1:2 and 5:6.

Now look at the triangles above the two lines, we have
(8+A):B=2:1 and (5+B):A=5:4

Cross-multiply and simplify, we have 2 equations in A and B:
2B-A=8
5A-4B=20
Solve them, you get A=12, B=10

So the unknown area = 22 arces

Hopefully this helps[/img]

[abhcbl]

I was trying to do a quick check on my son who is now in K1 … got him to try out the MO for Junior … and was surprise that he could do about 8 qns in test 1. He sort of good in math and science but his language skill were not good enough for him to really learn by himself.


Also I created a simple game for him to learn how to solve basic simultaneous equation, and he learn that in 1 day … he can now solve qns like "there are 15 more apples than oranges, and altogether there are 67 apples and oranges", and he had also complete the level 1 of Fan’s Math Processing. I look at most the math books available in popular, but they all look very dry (even I won’t enjoy them when I was young). Wondering anyone know of any good games/toys or things that could help a child to learn math in a much more fun way.

I hope to let him learn in a fun way … more about multiplication/division/fraction and time/speed/distant concept.

[andante]

Hi,

May I know whether there is any means to find the solution (not just answer key) for the SMOPS sample question ?

Thank you.

[andante]

Hi.

Is there any way to obtain the solution (not answer key) for SMOPS sample questions ?

Thank you.

[FrekiWang]

andante:

Hi,

May I know whether there is any means to find the solution (not just answer key) for the SMOPS sample question ?

Thank you.

I suppose you can just try GOOGLE it, but most likely you won't be able to get the full solution to all questions. Perhaps you can just post some of the problems which you are interested in knowing the full solution so that I can provide some help.

[CoffeeCat]

andante:

Hi.

Is there any way to obtain the solution (not answer key) for SMOPS sample questions ?

Thank you.

I believe you are referring to the sample questions on the HCI SMOPS website. The first one is the actual 2007 smops paper. You can buy the official booklet from centres like mathshub or learninginteractive i think.
The second one should be the actual 2009 paper i believe. I don't think hci published it. But I remembered AEP (Affinity Education Place) once mentioned they are selling it...