There are $n$ students with a different student number. Each student number is a positive factor of $60^{60}$

Question

In a school there are $n$ students, each with a different student number. Each student number is a positive factor of $60^{60},$ and the GCD of two student numbers is not a student number in the school. Find the greatest possible value of $n$.

I am completely lost in this problem. What should I do to solve it?

So far what I have done: $60^{60} = 2^{120}*3^{60}*5^{60}$

Each student number is of form: $2^{a}*3^{b}*5^{c} (0 \leq a \leq 120, 0 \leq b \leq 60,0 \leq c \leq 60)$

try this with smaller numbers? try maybe 21, then 24, then 72 , increase the complexity as you go and see a pattern — Sarvesh Ravichandran Iyer, May 31 '20 at 06:09
To find the number of factors that are students is it not as simple as taking the number of factors of the number and multiplying by two thirds and then finding the floor of that number? So: 300160. — atul ganju, May 31 '20 at 06:13
Do you mean the GCD of two distinct student numbers is not a student number? Or is it allowed for one number to divide another? — Aravind, May 31 '20 at 06:18
@астонвіллаолофмэллбэрг Which number should I change? — Ishraq Farhan, May 31 '20 at 06:25
The starting number. Imagine that all students had numbers that were divisors of $21$ instead, but the $\gcd$ condition remained, and try to get the answer in that case. — Sarvesh Ravichandran Iyer, May 31 '20 at 08:49
@астонвіллаолофмэллбэрг I am still lost. I do not know how to maximise the number of students — Ishraq Farhan, May 31 '20 at 10:35
IIRC, the 3-variable case had a much more complicated approach than the 2 variable case, esp if the GCD has to be that of a different student. — Calvin Lin, Jun 01 '20 at 20:02

score 1 · Answer 1 · answered Jun 01 '20 at 20:12

There's a slight/arguable ambiguity in the condition as to whether the 3 students need to be distinct, or the 3rd is allowed to be either the first or the second. We take the latter's interpretation.

Consider the lattice of points $(a, b, c)$ where $0 \leq a \leq 120, 0 \leq b \leq 60,0 \leq c \leq 60)$.
We define a partially ordered set where $(a_1, b_1, c_1) \leq (a_2, b_2, c_2 ) $ iff $ a_1 \leq a_2, b_1 \leq b_2 , c _1 \leq c_2 $.
The question asks for the size of the largest antichain.

Hint: By Dilworth's theorem states that the size of the largest antichain is equal to the minimum number of chains into which the set can be partitioned.

Observe that $X = \{ (120-b-c, b, c ) \}$ is an antichain of 3600 elements.
Conversely, we have 3600 chains that cover the lattice, namely $(0,b,c) -> (120, b, c)$.

Hence, the largest antichain has size 3600.

score 0 · Answer 2 · answered May 31 '20 at 08:05

HINT

We can start with two numbers, e.g. $5$ and $3.$ To be sure that GCD is not a student's number, combine increasing powers of one with decreasing powers of the other $$5^{60}3^{0}, 5^{59}3^1,\cdots,5^{0}3^{60}.$$ We have $61$ student numbers $$5^{60-k}3^k$$ until now.

There are $n$ students with a different student number. Each student number is a positive factor of $60^{60}$

2 Answers2