19th Eötvös Competition Problems 1912

1.  How many n-digit decimal integers have all digits 1, 2 or 3. How many also contain each of 1, 2, 3 at least once?

2.  Prove that 5ⁿ + 2 3^n-1 + 1 = 0 (mod 8).

3.  ABCD is a quadrilateral with vertices in that order. Prove that AC is perpendicular to BD iff AB² + CD² = BC² + DA². 

Solutions

Problem 1

How many n-digit decimal integers have all digits 1, 2 or 3. How many also contain each of 1, 2, 3 at least once?

Solution

3 choices for each digit, so 3ⁿ in all.

We must exclude the 2ⁿ with all digits 1 or 2, and the 2ⁿ with all digits 2 or 3, and the 2ⁿ with all digits 1 or 3. But then we exclude twice those with all digits 1, all digits 2 and all digits 3. Hence 3ⁿ - 3·2ⁿ + 3. 

Problem 2

Prove that 5ⁿ + 2 3^n-1 + 1 = 0 (mod 8).

Solution

If n is even, 5ⁿ = 1 mod 8, 3^n-1 = 3 mod 8, so expression = 1 + 6 + 1 = 0 mod 8. If n is odd, then 5ⁿ = 5 mod 8, 3^n-1 = 1 mod 8, so expression = 5 + 2 + 1 = 0 mod 8. 

Problem 3

ABCD is a quadrilateral with vertices in that order. Prove that AC is perpendicular to BD iff AB² + CD² = BC² + DA².

Solution

Let the diagonals intersect at O and put ∠AOB = x. Then AB² = OA² + OB² - 2·OA·OB cos x, CD² = OC² + OD² - 2·OC·OD cos x. So AB² + CD² = OA² + OB² + OC² + OD² - 2 cos x (OA·OB + OC·OD). Similarly, BC² + DA² = OA² + OB² + OC² + OD² + 2 cos x (OA·OD + OB·OC). Thus if x = 90^o, then cos x = 0 and AB² + CD² = BC² + DA². But if x ≠ 90^o, then cos x ≠ 0 and so AB² + CD² and BC² + DA² are on opposite sides of OA² + OB² + OC² + OD² and hence unequal.