7
$\begingroup$

MIT's Baker House has a tradition of dropping an irrepairable piano six floors every Drop Day, the last day one can drop a class without penalty (the 2022 date is 19 April). This year, in order to prevent damage to the asphalt, you have been asked to erect a net to catch the piano as a hack.

Being a hack, your large net must be made of

  • 23 aluminium poles for support
  • 23 small nets, each consisting of five rings that can be threaded onto the poles, connected by elastic ropes in all possible ways (hence $\binom52=10$ ropes per small net)

To maximise the large net's strength everything should be used, while each small net should span five different poles and no two small nets should span two poles in common (i.e. each pair of poles is spanned by at most one small net). Baker House residents say you can do this, since the total number of ropes is $23\binom52=230$, less than the number of slots for ropes which is $\binom{23}2=253$.

  1. Find a solution to the task (an assignment of poles spanned to each small net).
  2. Is that solution unique up to permuting the poles and small nets? ( does not apply for this one.)
$\endgroup$
1
  • $\begingroup$ Yeah, ok, but now how do you prove your solution is sufficient to prevent damage to the asphault? (yeah I know I'm being laterally concrete (pun intended) ). We need to estimate the maximum force the asphault can take without damage, the mass of the piano, the height of the poles, the elastic coefficient of the ropes. :-) $\endgroup$ Jan 28 at 12:18

1 Answer 1

14
$\begingroup$

One straightforward way to arrange the nets for question 1 is as follows:

Number the poles $0$ to $22$.

For each number from $i=0$ to $i=22$ put one net between the poles $i$, $i+3$, $i+4$, $i+9$, and $i+11$, all taken modulo $23$.
Note that the $10$ distances between the poles connected by a net are all distinct (1, 2, 3, 4, 5, 6, 7, 8, 9, and 11) and therefore no two nets have any pair of poles in common.

Here are some thoughts on question 2:

Every net contributes four ropes (edges) to each pole (vertex). So each vertex has degree at most 20, and given the number of edges there are in total, every vertex must have degree exactly 20. This means that each vertex is not linked to exactly two other vertices, and so those missing edges (i.e. the complement graph) consist of cycles.
My answer to question 1 has as its complement graph a single cycle with all the edges spanning 10 vertices, the only length missing from a single net. The vertices can be permuted to make the missing length any other value. It is not clear to me whether all solutions where the complement is a single cycle are equivalent. It might be possible that there are two different nets that cover the same set of 10 distances. It might even be possible that there is some solution with nets that are not all of the same type, or one where the complement consists of more than one cycle.

$\endgroup$
2
  • 2
    $\begingroup$ How straightforward, and nearly not brilliant at all.~:-) $\endgroup$
    – Bass
    Jan 28 at 9:15
  • $\begingroup$ In fact the packing is unique. $\endgroup$ Jan 29 at 21:20

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.