3
$\begingroup$

You would like to sort some monthly magazines in different categories.

Disregarding the title of magazines, there are 4 different categories if you arrange magazines by publishing year and month.

Disregarding the publishing year, there are 5 different categories if you sort magazines by title and month.

Disregarding month, you could divide magazines in to 6 different categories if you sort magazines by title and publishing year.

How many monthly magazines you have at most?

There is no magazine with the same title, publishing year and month. Each categorization does not need to have the same number of magazines.

Improve this question
$\endgroup$
  • $\begingroup$ Sorry. I added "at most" to the question. $\endgroup$ – P.-S. Park Jan 30 '15 at 17:47
6
$\begingroup$

10 mayhaps?

enter image description here

The picture corresponds with the magazines in the natural way. Projections along the three axes have sizes 4, 5, and 6.

I conjecture that with $a$, $b$, and $c$ categories in the three axes, the maximum number of magazines is at most $\sqrt{abc}$.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ I like the visualization. $\endgroup$ – JonTheMon Jan 30 '15 at 18:06
  • 1
    $\begingroup$ Stunning visualization, requires hardly any explanation. On the conjecture, you probably mean "With $a$, $b$, and $c$ categories in the projections along the three axes, the maximum number of magazines is at most $\sqrt{abc}$."? $\endgroup$ – Johannes Jan 30 '15 at 18:42
  • $\begingroup$ I like it, too. As Lopsy conjectured, the number of magazines is at most $\sqrt{abc}$. This was the problem #5 in International Math. Olympiad 1992. $\endgroup$ – P.-S. Park Jan 31 '15 at 1:06
  • $\begingroup$ I conjecture that with $D$ classifiers, and $a_1$, $a_2$, .. , $a_D$ categories for each of the cases in which one classifier is ignored, the number of magazines is at most $(a_1 a_2 .. a_D)^{1/(D-1)}$. $\endgroup$ – Johannes Jan 31 '15 at 12:13
1
$\begingroup$

Welp, looks like I can max out at 10 mags:

a 2000 jan
b 2000 jan
c 2000 jan
a 2001 jan
b 2001 jan
c 2001 jan
a 2000 feb
b 2000 feb
a 2001 feb
b 2001 feb

Old:
I think 6 would be the number of magazines. 

a 2000 Jan  or  a 2000 Jan
b 2000 Feb      b 2000 Feb
c 2000 Jan      c 2000 Mar
d 2000 Feb      d 2000 Jan
a 2001 Jan      e 2000 Jan
b 2001 May      a 2001 Jan

Any repeating combo of attributes would increase one of the other groups.

We have to cross over 2 years, since one year with the #6 means you'd need 6 different mags, which would completely bork #5, which directly says we have a repeating title-month.

We have to have 2 repeating year-month combos, and one repeating title-month combo, which are mutually exclusive. So, that means we have at most 3 distinct months. We can achieve the 4 year-month combos with 2 years and 2 months if desired.

So what about a repeating title-year? Well, that would increase the title-month count, so we can't have that. So, 6 magazines.

Improve this answer
$\endgroup$
  • $\begingroup$ You can do it with only 2 months. In your second example you can have c 2001 Feb instead of c 2000 Mar and still meet all the criteria. $\endgroup$ – Togashi Jan 30 '15 at 17:37
  • $\begingroup$ That would reduce the year-month count to 3. $\endgroup$ – JonTheMon Jan 30 '15 at 17:39
  • $\begingroup$ Nope, you still have Jan 2000, Feb 2000, Jan 2001, and Feb 2001. $\endgroup$ – Togashi Jan 30 '15 at 17:39
  • $\begingroup$ Ah, right. I'll adjust that. $\endgroup$ – JonTheMon Jan 30 '15 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.