Maths Olympiad Prep

Library / /12 of 27

Number theory Difficulty 6.3 National olympiad Find the answer

The set of {1,2,3,...,63}\{1,2,3,...,63\} was divided into three non-empty disjoint sets A,BA,B. Let a,b,ca,b,c be the product of all numbers in each set A,B,CA,B,C respectively and finally we have determined the greatest common divisor of these three products. What was the biggest result we could get?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given the problem, we need to divide the set {1,2,3,,63}\{1, 2, 3, \ldots, 63\} into three non-empty disjoint sets AA, BB, and CC. Let the product of the numbers in these sets be aa, bb, and cc, respectively. We aim to maximize the greatest common divisor (GCD) of these three products, gcd(a,b,c)\gcd(a, b, c).

First, calculate the product of all numbers from 1 to 63:

P=12363=63! P = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot 63 = 63!

Since AA, BB, and CC together contain each of the numbers exactly once, their combined product is also 63!63!. Therefore:

abc=63! a \cdot b \cdot c = 63!

To find gcd(a,b,c)\gcd(a, b, c), we consider the prime factorizations. We utilize the principle that the GCD is maximized when the prime factors are evenly distributed among aa, bb, and cc.

Calculate the prime factorization of 63!63!. For a prime pp, the exponent of pp in 63!63! is given by:

ep=63p+63p2+63p3+ e_p = \left\lfloor \frac{63}{p} \right\rfloor + \left\lfloor \frac{63}{p^2} \right\rfloor + \left\lfloor \frac{63}{p^3} \right\rfloor + \cdots

Compute for each prime number up to 63:

- Prime 2:
e2=632+634+638+6316+6332=31+15+7+3+1=57 e_2 = \left\lfloor \frac{63}{2} \right\rfloor + \left\lfloor \frac{63}{4} \right\rfloor + \left\lfloor \frac{63}{8} \right\rfloor + \left\lfloor \frac{63}{16} \right\rfloor + \left\lfloor \frac{63}{32} \right\rfloor = 31 + 15 + 7 + 3 + 1 = 57

- Prime 3:
e3=633+639+6327=21+7+2=30 e_3 = \left\lfloor \frac{63}{3} \right\rfloor + \left\lfloor \frac{63}{9} \right\rfloor + \left\lfloor \frac{63}{27} \right\rfloor = 21 + 7 + 2 = 30

- Prime 5:
e5=635+6325=12+2=14 e_5 = \left\lfloor \frac{63}{5} \right\rfloor + \left\lfloor \frac{63}{25} \right\rfloor = 12 + 2 = 14

- Prime 7:
e7=637+6349=9+1=10 e_7 = \left\lfloor \frac{63}{7} \right\rfloor + \left\lfloor \frac{63}{49} \right\rfloor = 9 + 1 = 10

- Higher Primes:
Simply calculate based on the limited number of occurrences up to 63.

Distribute these exponents evenly among aa, bb, and cc to maximize the GCD. Note that if a certain power cannot be distributed evenly, a small remainder may be distributed among one or two products, minimizing impact on the GCD:

- Exponents Distribution:
- 2: Divide 5757 into 19+19+1919 + 19 + 19
- 3: Divide 3030 into 10+10+1010 + 10 + 10
- 5: Divide 1414 into 4+5+54 + 5 + 5 or another combination maximizing GCD
- Continue similarly for all smaller primes up to 63.

The resulting maximum GCD, evenly distributing prime factors, would be:

219310547311131719 \boxed{2^{19} \cdot 3^{10} \cdot 5^4 \cdot 7^3 \cdot 11 \cdot 13 \cdot 17 \cdot 19}

Where the excess factors are allocated optimally for maximizing the GCD.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.