Non-divisible Factors Of 2016

Probability Level 4

Let $F$ be the set of all positive integer factors of 2016.

Let $S$ be a subset of $F$ with the following property:

For any pair of distinct elements $a$ and $b$ in $S$ , $a\nmid b$ and $b\nmid a$ .

What is the maximum value of $|S|$ ?

The answer is 6.

2 solutions

Andy Hayes
Sep 12, 2016

Below is a Hasse Diagram of the factors of $2016$ , organized by divisibility:

The subsets which satisfy the property for $S$ contain elements that are in parallel paths in the diagram. One can see that the largest possible subset would have $|S|=\boxed{6}$ . An example subset which has this property is $\{32,48,72,112,168,252\}$ .

I didn't know about these diagrams, so thanks for posting the question. Great wiki, by the way. :)

Brian Charlesworth - 4 years, 9 months ago

It is a very good wiki, but it's not mine! It was written by @Patrick Corn . I was inspired by it to write this question.

Andy Hayes - 4 years, 9 months ago

Thanks! I wonder what the general answer is, or if there are some partial results. It's not immediately obvious how to generalize...

Patrick Corn - 4 years, 9 months ago

@Patrick Corn – @Mark Hennings gives a generalization in his solution.

Andy Hayes - 4 years, 9 months ago

Does |S| mean the maximum number of elements of S I was confused what the problem was asking for (I don't understand the notation so it's really my own fault, but still)

Alex Li - 4 years, 9 months ago

The vertical bars indicate the cardinality (size) of the set. $|S|$ represents how many elements the set $S$ has. The problem is asking for the maximum number of elements $S$ can have.

Andy Hayes - 4 years, 9 months ago

Mark Hennings
Sep 14, 2016

If $N$ is a product of $m$ primes, then a maximal antichain for the positive integer factors of $N$ under division is equal to

if $m = 2k$ , the divisors of $N$ which are products of $k$ primes,
if $m=2k+1$ , either the divisors of $N$ which are products of $k$ primes, or the divisors of $N$ which are products of $k+1$ primes.

Since $2016 = 2^5 \times 3^2 \times 7$ , it is a product of $8$ primes. A maximal antichain in $F$ is the set of divisors of $2016$ which are products of $4$ primes, namely $16,24,56,36,84,126$ . Thus the answer is $6$ .

Is that obvious? It looks like Sperner's theorem (and is the same as Sperner's theorem if $N$ is the product of distinct primes), but I don't quite understand why it's true in general.

Hmm, it appears to be a theorem of DeBruijn/Tengbergen/Kruyswijk from 1951, but I don't have the reference in front of me.

Patrick Corn - 4 years, 9 months ago

Indeed! It is an extension of Sperner's Theorem. The reference is

N. G. de Bruijn, Ca. van Ebbenhorst Tengbergen, and D. Kruyswijk, On the set of divisors of a number, Nieuw Arch. Wiskunde (2) 23 (1951), 191–193.

and the paper can be found here . I have changed the link, @Patrick Corn ; the old one seems to have broken.This is the authors' free access copy.

Mark Hennings - 4 years, 9 months ago

What happens if there would be 2015^200 instead of 2016?Please give your solution with more details.

Akash Hossain - 3 years ago

Non-divisible Factors Of 2016

The answer is 6.

2 solutions

0 pending reports