Maths Olympiad Prep

Library / /99 of 520

Combinatorics Difficulty 6.5 National olympiad Find the answer

Stars can fall in one of seven stellar classifications. The constellation Leo contains 99 stars and 1010 line segments, as shown in the diagram, with stars connected by line segments having distinct stellar classifications. Let nn be the number of valid stellar classifications of the 99 stars. Compute the number of positive integer divisors of nn.
[img]https://cdn.artofproblemsolving.com/attachments/9/c/ba1cad726bc62038686a0af408e2fe60dfbde6.png[/img]

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

Solution

1. Understanding the problem: We need to find the number of valid stellar classifications for the 9 stars in the constellation Leo, where each star has a distinct classification from its connected stars. Then, we need to compute the number of positive integer divisors of this number.

2. Analyzing the pentagon subset: Consider the 5-star pentagon subset of the constellation, denoted as ABCDEABCDE. We need to classify these stars such that no two connected stars have the same classification.

3. **Classifying AA and BB**: There are 7 possible classifications for AA and 6 remaining classifications for BB, giving us 7×6=427 \times 6 = 42 ways to classify AA and BB.

4. **Classifying DD:
-
Case 1**: DD has the same classification as AA or BB. There are 2 choices for DD (same as AA or BB), 6 choices for CC (different from AA and BB), and 5 choices for EE (different from AA, BB, and CC). This gives 2×6×5=602 \times 6 \times 5 = 60 ways.
- Case 2: DD has a different classification from AA and BB. There are 5 choices for DD, 5 choices for CC (different from AA, BB, and DD), and 5 choices for EE (different from AA, BB, CC, and DD). This gives 5×5×5=1255 \times 5 \times 5 = 125 ways.

5. Total classifications for the pentagon: Summing the two cases, we get 60+125=18560 + 125 = 185 ways to classify the pentagon given the classifications of AA and BB. Therefore, the total number of valid classifications for the pentagon is 42×185=777042 \times 185 = 7770.

6. Classifying the remaining 4 stars: Each of the remaining 4 stars can be classified in 6 ways (since they are connected to at most 3 other stars, and there are 7 classifications in total). Thus, the total number of valid classifications for the entire constellation is:
7770×64=7770×1296=10077120 7770 \times 6^4 = 7770 \times 1296 = 10077120

7. Finding the number of positive integer divisors: To find the number of positive integer divisors of 1007712010077120, we need its prime factorization:
10077120=27×34×51×71 10077120 = 2^7 \times 3^4 \times 5^1 \times 7^1
The number of positive integer divisors is given by multiplying the incremented exponents:
(7+1)(4+1)(1+1)(1+1)=8×5×2×2=160 (7+1)(4+1)(1+1)(1+1) = 8 \times 5 \times 2 \times 2 = 160

The final answer is 160\boxed{160}

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.