This School Is Weird!
In a school, each student is assigned a positive factor of 6 0 6 0 , but no student's number is the greatest common divisor of any two student numbers (one of which may be their own).
What is the maximum number of students in this school?
The answer is 3721.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
(This comment isn't true. I'm leaving it up just in case someone makes that same mistake. We do have a double-sided implication.)
First note that "the GCD of two student numbers is not a student number" is equivalent to "No student number divides another student number"
That is not true. What we have is "No student number divides another student number" implies "the GCD of two student numbers is not a student number", but not vice versa.
Thus, you have a more restrictive condition, hence have found a lower bound on the maximum.
Log in to reply
I'm assuming you interpreted it as "the GCD of two student numbers is not a [third, distinct] student number."
In that interpretation, you would be right for my having only proven a lower bound. I'm not sure right now how you would solve the resulting problem, but it surely would be interesting.
For example, I don't have a proof, but in the case of a Boolean lattice (as in Sperner's theorem), I'm pretty sure my lower bound would still be the answer. In general, though, I don't even know if this lower bound can be strict for any finite graded lattice.
Log in to reply
In your construction, with a = 1 2 0 − b − c
you could add at least one more student with the number 1, ( a , b , c ) = ( 0 , 0 , 0 )
Log in to reply
@Darko Simonovic – g cd ( 2 1 2 0 , 3 6 0 5 6 0 ) = 1 , so we can't add 1 .
It does occur to me that I missed the obvious though. A finite chain would be admissible in its entirety under the alternative interpretation, while obviously the maximum size of an antichain would be 1 , so it's strict then.
I thought this was an interesting comment because I think it shows how the language of a problem can cause us to take certain intuitions we have about what is going on in a problem for granted. When I saw this comment at least, I interpreted the following way: Consider the numbers 6 and 15. They have gcd(6, 15) = 3. Of course a priori there is no reason they can't coexist in the set together, and neither one divides the other. I.E. if two numbers share a common divisor, they do not necessarily divide each other, and it is this statement that makes it feel as if Brian's solution should only be a lower bound because he restricted his proof to the case where numbers cannot divide each other. However, this does not contradict Brian's statement and I think using clearer statements will make the meaning a bit more obvious.
Consider a set S with the property that if a and b are in S, then (a,b) is not in S. We want to show this statement is equivalent to the following condition on S. If a is in S and b|a, then b is not in S.
To show the forward direction, suppose for contradiction there exists a in S and b s.t. b|a and b in S i.e. suppose condition two is not satisfied. Then note that the first property is not satisfied since (a,b) = b is in S, which is a contradiction.
To show the backwards direction, we have that (a,x)|a and hence is not in S. Thus (a,x) cannot be in S.
This was at least the sort of logical fumbling I needed to do to rectify the situation after seeing the comment. Of course I could have misinterpreted it.
Maybe you should give a link to the result you state without proof about the size of a maximal antichain in the set of positive divisors of n --I don't think the result is particularly obvious!
Also, for enumeration, it's easier just to note that any pair b , c gives a unique a , b , c , so the answer is just 6 1 ⋅ 6 1 = 3 7 2 1 .
Log in to reply
Thanks for the comments.
I agree I should source that statement. I just didn't know how to go about doing that without completely breaking the flow of the solution (I've been spoiled by BibTeX), which is why I compromised by at least giving the mathematical rephrasing of the question so that people could search for it efficiently. As far as I could tell, the first publicized proof appeared in
Bruijn, de, N.G. ; Ebbenhorst Tengbergen, van, C. ; Kruyswijk, D
On the set of divisors of a number. In: Nieuw Archief voor Wiskunde. 1951 ; Vol. serie 2, 23. pp. 191-193
Here's a link to the text (see theorem 1 and its proof): https://pure.tue.nl/ws/portalfiles/portal/4373475
As for your second comment, yes, that is much easier. Can I use that in my solution?
Log in to reply
Sure. And you can link by typing the word you want to link in square brackets and then typing the link in parentheses (no spaces in between).
Log in to reply
@Patrick Corn – Thanks. That cleaned it up quite a bit.
I never likes chains, either. I have always been an antichain. Rope is far more efficiant.
Log in to reply
Cute. I actually hadn't heard that one before.
I don't understand how this works...
For example fix a and b and allow c = x to vary over a desired range so now we have, n = n ( x ) = 2 a 3 b 5 x .
Note that for every n ( x ) we have n ( x ) ∣ n ( x + 1 ) whatever be the value of a and b . So for n ( x ) to not divide n ( x + 1 ) we need to find the largest term in the sequece { x } = { 1 , 2 , 3 , . . . , 6 0 } This leads to the conclusion that for each pair of ( a , b ) we obtain a unique c . How does this lead to 3721 solutions?
Log in to reply
For a given a and b there can be only one c in the set, true. The antichain with 3 7 2 1 members is given, as the solution says, by numbers n of the form 2 a 3 b 5 c with a + b + c = 1 2 0 . It's not hard to see that none of them can divide each other (i.e. they form an antichain); it's significantly harder to see that they are the maximal such set, which is what the linked article proves.
The question is worded vaguely.
-
It does not state that the student numbers must be unique, resulting in a posssibly infinite number of students (give each student the number 2).
-
It seems to imply that the rule is: "the gcd of two student numbers can't be a third distinct student number", resulting in a possibly different answer.
It's a very interesting problem tho, and I like the solution.
Log in to reply
In your first case, the gcd of any two students is 2, which is the value of another student's number so this is invalid. I agree with your second point, although I don't know if this affects the final result.
I... actually agree with your second point. Somewhere between the original posting and maybe when it posted as a featured problem, the wording was edited [for clarity?], but now that's a reasonable interpretation due almost entirely to placement of the word "other" in the current version. As Calvin Lin originally posted, this means my answer is only a lower bound. It's strict, too, as we could at least add 6 0 6 0 to the school and it still would work under that interpretation.
The question said that "...of any OTHER two ...". To me this means that if the student number isn't one of the two student numbers then it isn't their GCD, however it allows it to be de GCD if it's one of the two numbers. For example if one students number is 3, and anothers is 6, then that doesn't violate the rules, because even though 3 IS the GCD of 3 and 6, it's one of the two numbers.
Log in to reply
This was due to a word change sometime after I posted my solution (note for instance that my quotation no longer appears in the problem statement)
Under that alternate interpretation, I currently don't know the answer. My guess is that it would be the union of antichains, using the one I named in the solution and a few higher-rank ones as well, but this is pure guesswork--I wouldn't dare even call it "conjecture".
My interpretation of the question was that the GCD was allowed if not used. For example if 6 and 10 were used then 2 would not be allowed and similarly if 2 and 6 were used then 10 not allowed etc. I found using computation for N=60 there was a maximum of 7, N=60^2 it was 18 and could go no further as this is the Set Cover problem. So I gave up to look at the solution to find my interpretation challenged. Although I fail to see how my interpration can be considered wrong given the wording of the problem.
Log in to reply
I see the wording has changed (removing of any other). Lesson learn: don't attempt a puzzle until it's a month old and been vetted by the community
Log in to reply
Yea, I just changed the wording of the problem, given the comments.
First note that "the GCD of two student numbers is not a student number" is equivalent to "No student number divides another student number". Therefore, using mathematical terminology, the possible sets of student numbers in the school are precisely the antichains of the divisor lattice of all the divisors of 6 0 6 0 .
Additionally, we note that 6 0 6 0 = 2 1 2 0 3 6 0 5 6 0 and the sum of the exponents is 1 2 0 + 6 0 + 6 0 = 2 4 0 . Therefore, by Theorem 1 of this article , the maximum size of an antichain is attained by all divisors of the form 2 a 3 b 5 c such that a + b + c = ⌊ 2 2 4 0 ⌋ = 1 2 0 .
(Thanks to Patrick Corn for pointing out the following to me. It's much simpler than my original method)
To count the number of non-negative integer solutions to a + b + c = 1 2 0 such that b , c ≤ 6 0 (which are in natural correspondence to the antichain mentioned above), we select b , c each freely from { 0 , 1 , 2 , … , 6 0 } and then note that a = 1 2 0 − b − c ≥ 1 2 0 − 6 0 − 6 0 = 0 . Since each of b , c has 6 1 possible values, it follows that there are 6 1 ⋅ 6 1 = 3 7 2 1 possible integer solutions.
Therefore the maximum size for n is max n = 3 7 2 1