For those unaware, there is a sheet given to those who qualified for this year's BMO1 and it contains 30 problems of varying difficulty.

I would like to know if my answers are correct:

Q) How many positive integers less than 2002 are divisible by 3,5 or 7?

Q) What is the highest power of 3 that divides 100!?

Q)

(1) The numbers up to 2002 can be divided into blocks of 105, by chinese remainder theorem.

It is easy to inspect each 105, and i find there to be 12 repeated numbers (105 repeated tice) and so the distinct numbers that are multiples of 3,5, or 7 count to 57.

there are 19 units of 105, and from 1995 to 2002 there are a further 3 (or 4 if you include 2002) hence I get 1083+3or4.

I believe that the highest power of 3 to divide 100! is [100/3]+[100/9]+[100/27]+[100/81]=33+11+3+1=48 This can be seen easily from Legendre's Formula: http://mathworld.wolfram.com/LegendresFormula.html
When I first met this (a couple of days ago!) I was amazed by the simplicity and power of this formula... and also pleased to find a use for the "greatest integer function". I found this result whilst studying "Elementary Number Theory" by David M. Burton (thanks for the tip Yatir!).

1. yep, 1086 is what I have

2. I found 3⁴⁸ , since we are trying to find how many powers of 3 divides into 100!=1 x 2 x 3 x ... x 100. So in effect we are trying to find how many times we can write 3 x 3 x3... x 3 in 100!. There are 33 of 3s, then 11 of 9s (since 9=3 x 3, one of them are counted in the 33, but the other needs to be counted), 3 of 27 and 1 of 81. 33+11+3+1=48. Does anyone else agree on this or have I made any mistake or not totally understood the question?

3. this site here gives a brilliant prove. All you need is Pythagoras and basic algebra (a lot of algebra! so I wont do it again here)

Philip, That's the name of the formula...I always get mixed up between legendre, lagrange and laplace...

Regarding question 1, people might like to investigate the inclusion-exclusion formula/principle, another case of, in my opinion, giving a fancy name to the (fairly) obvious.

Vicky

Of course the legendre's formula (I knew it with a different name that I can't remember now) can be proved with the inclussion-exclusion principle. Alngelina is almost there (for this case) however the correct argument is this:
There are 33 powers of 3 dividing 100! (1)
there are 9 powers of 9 dividing 100! (2)
there are 3 powers of 27 dividing 100! (3)
there is 1 power of 81 dividing 100! (4)
Now the exact reasoning:
There are 33-9 powers of 3 dividing 100! from which none of them is a power of 9 (or higher)
Similarly 9-3 powers of 3² dividing 100! none of them a power of 27 etc.
Now add them (33-9) + 2(9-3) + 3(3-1) + 4.1 = 33 + 9 + 3 + 1 = 48

(I have a 2(9-3) because a power of 9 is a power of 3² etc.)

Please tell me if anything here is not clear

Demetres

I think this is not actually Legendre's formula. The Mathworld link someone gave above is to an entirely different formula (with a superficial similarity, i.e. it involves floor functions and inclusion-exclusion).

As for Heron's formula, the two proofs we have seen in the thread (mine and the one on Angelina's link) are in fact more or less the same, except the site includes a proof of the cosine rule within the proof: p is just a cos B, and the cosine rule gives the same expression for p much more quickly. As for the factorisation step, h² = a² - p² is just sin² B = 1 - cos² B, since h = a sin B. So they are ultimately exactly the same proof; but it saves you some work if you quote the cosine rule. (Not that it isn't worth knowing how to prove the cos rule, of course.)

David

I think the formula used in Q2 is called de Polignac's formula.

Demetres

There's another way to solve the Heron's Formula that basically includes circles and quite simple. The main idea is to use the in-contact circle and the formulas that are related to it.

Take a look at this:

We have:
Triangle ABC
a, b, c are the length of BC, AC, AB
2p is the perimeter of the triangle
S is the Area of the triangle
r is the radius of the in-contact circle (the center of this circle is where the 3 inner angle-bisector meet)
rA, rB, rC are the radius of the half-in-contact circle of the angle A, B and C respectively. (the center of the half-in-contact circle of the angle A is where the inner angle-bisector of the angle A and the outer angle-bisector of the angle B and C meet) (the outer angle-bisector of an angle is perpendicular to the inner angle-bisector of that angle).

The in-contact circle touches BC, AC, AB at D, E and F respectively.
The half-in-contact circle of the angle A touches AB at F' and AC at E'.

Prove that:
a) S = pr = (p-a)rA = (p-b)rB = (p-c)rC
b)

They're generally known as the incircle and the A/B/C-excircles respectively (the A-excircle is tangent to side BC and the extensions of AB and AC)

David

[1 and 2 are easy when you draw a picture]

Now put all these together (recall the formula for tan(a+b))

Demetres

About Heron formula you can read example here .

Peter