21
$\begingroup$

From May 2012, Communications of the ACM (wording reverse-engineered from the solution given in the June 2012 edition as I don't have the May 2012 edition handy).

Given a 5x5 grid of boxes, place diagonals within the boxes such that:

  1. each diagonal connects opposite corners of one of the 25 boxes;
  2. each box contains at most one diagonal; and
  3. each grid intersection (i.e. box corner) can have at most 1 diagonal touching it.

Example:

enter image description here

In the grid above, the diagonal at the top-left is ok. The top-left box has 2 corners with 1 diagonal touching and 2 corners with 0 diagonals touching. Note that the box on its right cannot have a NW-SE diagonal ('\') since the NW corner already touches a diagonal). The 2 red diagonals can't both be used because they touch a common grid intersection. You can flip one of the red diagonals so they are arranged like '//' or '\\' (either way would be ok in this example), or drop one or both of them.

Challenge: find the maximum number of diagonals that can be placed to satisfy the conditions, and prove that the number you found is maximal.

Improve this question
$\endgroup$

6 Answers 6

Reset to default
13
$\begingroup$

A weak upper bound

There are 36 intersections, so that gives an upper bound of 18 diagonals.

Strengthening the upper bound

Look at the top row of six intersections. There are only five diagonals (maximum) in the top row of squares, and each diagonal in the top row of squares uses at most one intersection, so at least one of the top row intersections must be unused. Similar logic holds for the bottom row, so there can be at most 17 diagonals.

Strengthening once more

Can we reach 17? Let's see:
Assume WLOG that the bottom left and top right intersections are the only unused ones. (We need two unused intersections, at least one of which is in each outer row/column.) To place 17 slashes, we would have to use every intersection but those two.
enter image description here
To use the top left corner, A1 must have a \. To use the one just below of that, A2 must have a \. This continues down the left column until we reach A5. At this point all the intersection in the left column have been used but one.

The same reasoning, applied to the other outer rows and columns, says that all of the border is filled with \s. However, this causes D1 and E2 to both have a \, so that is impossible. Therefore 16 is our new upper bound.

Finally...

16 is achievable through Jaap Schierphuis' answer, so it is the maximum. ■

Improve this answer
$\endgroup$
5
  • $\begingroup$ ... aaand Deusovi strikes again. Congratulations! :) $\endgroup$
    – Lawrence
    Commented Feb 19, 2018 at 14:22
  • 2
    $\begingroup$ @Lawrence Thank you! I had 16 for a while, but was holding off on posting because I thought 15 was the maximum, and I kept trying to strengthen the bound again. That worked exactly as well as you'd expect, considering that the statement I was attempting to prove was false. :P $\endgroup$
    – Deusovi ♦
    Commented Feb 19, 2018 at 14:23
  • $\begingroup$ (I tried a parity argument based on turning the board diagonally and using a domino tiling, but that didn't account for not being able to put both slashes in one square.) $\endgroup$
    – Deusovi ♦
    Commented Feb 19, 2018 at 14:24
  • $\begingroup$ Most of the critical elements of CACM's solution were covered by the answers here. If anyone's interested, here's a sketch. They produced a 16-diagonal answer by construction (identical to @Jaap's up to symmetry) and noted the max 18-diagonal (cf @Evergalo). 5 boxes per perimeter side meant max 5 corners per side, which could conceivably be scrunched into just 2 diagonal corners (of the big square). But that would leave the D1-E2 problem you noted, so at least 3 corners would be untouched, leaving at most 36-3=33 corners used, which with 2 corners per diagonal produces a max of 16 diagonals. $\endgroup$
    – Lawrence
    Commented Feb 19, 2018 at 14:38
  • $\begingroup$ I like answers to be visible without having to click on boxes, though I'm aware that others like them hidden. Since the text of this answer takes some thinking through, answer-hiding doesn't achieve all that much for this question. Would it be objectionable to request that the spoilers be lifted? $\endgroup$
    – Lawrence
    Commented Feb 19, 2018 at 14:42
22
$\begingroup$

I found an arrangement with

16

diagonals, but a proof of optimality still eludes me.

Here is a picture of the arrangement:

enter image description here

Improve this answer
$\endgroup$
7
  • 8
    $\begingroup$ @Untitpoi I know, it's unfortunate. I can never remember which direction a swastika goes, but I'm not going to look it up on my work computer. $\endgroup$
    – Jaap Scherphuis
    Commented Feb 19, 2018 at 14:09
  • 1
    $\begingroup$ +1 Well done! This was perhaps the most difficult part, but Deusovi presented a complete answer so gets the green tick. $\endgroup$
    – Lawrence
    Commented Feb 19, 2018 at 14:23
  • 1
    $\begingroup$ And a +1 from me too - nice find! I was convinced it was impossible. $\endgroup$
    – Deusovi ♦
    Commented Feb 19, 2018 at 14:25
  • 3
    $\begingroup$ @JaapScherphuis: Swastikas predate the Nazi party by millennia, I don't think aversion from the shape is justified. For reference, swastikas can be either right- or left- facing, the Nazis used a right-facing one like the one currently depicted, but rotated 45 degrees. $\endgroup$
    – Meni Rosenfeld
    Commented Feb 19, 2018 at 14:35
  • 8
    $\begingroup$ @JaapScherphuis To check the direction without having it in your search history, try image searching "comcast reddit" $\endgroup$
    – phflack
    Commented Feb 19, 2018 at 14:43
5
$\begingroup$

As a starter:

There are $6*6=36$ boxes' corners.

Each diagonal connects two corners.

Thus we have an upper bound of $36/2=18$ diagonals.

It is easy to achieve $15$ diagonals: just place NW-SE diagonals in each box in the first, third and fifth columns.

Thus we have a lower bound of $15$ diagonals.

My intuition is that it is impossible to stack more than 15 diagonals and that there should be an easy, visual, geometric proof for that. But that proof still escapes me.

edit: as usual, my intuition proved wrong. See Jaap's nice solution.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Each two rows of 12 'dots' must have 2 wasted dots, one at each end. There are 3 rows of 12 'dots'. 36 - 6 = 30. 15 diagonals would use all dots. $\endgroup$
    – HollyLeaves
    Commented Feb 19, 2018 at 13:55
  • $\begingroup$ My answer shows that 15 is not the maximum achievable, so @HollyLeaves's argument does not work in general - the assertion that every pair of rows of intersections must have two wasted dots does not hold. $\endgroup$
    – Jaap Scherphuis
    Commented Feb 19, 2018 at 14:06
  • 1
    $\begingroup$ +1 Nice insight on the number of box corners constraining the number of diagonals. $\endgroup$
    – Lawrence
    Commented Feb 19, 2018 at 14:24
  • $\begingroup$ You're right, that's a very clever solution. $\endgroup$
    – HollyLeaves
    Commented Feb 19, 2018 at 14:24
2
$\begingroup$

The answer is

16

You can find example is in one of the previous answers.

Let us show now that we can’t get more

Suppose we got 17 diagonals. Notice that any rectangle 2*5 contains at most 6 diagonals, because it has exactly 6 intersections on it’s middle line. Consider now low rectangle and upper one. They both have at most 12 diagonals thus middle rectangle 1*5 has to have all 5 diagonals. Similarly, we can show that vertical middle rectangle 1*5 has to contain all 5 diagonals. WLOG let those diagonal be SW-NE. This yields the contradiction because diagonals in squares C2 and B3 have common intersection.

Improve this answer
$\endgroup$
1
$\begingroup$

You can't get 18:

Every box has all 4 corners occupied, but the corners of the grid force a different story...

Improve this answer
$\endgroup$
1
$\begingroup$

I'd go with

16
There are 16 inner grid intersections and you can have at most one diagonal per intersection.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The corner boxes can have diagonals that does not use an inner grid intersection. $\endgroup$
    – Jaap Scherphuis
    Commented Feb 19, 2018 at 13:23
  • $\begingroup$ You are right, my proof doesn't hold water. But at least I got the number correct! $\endgroup$
    – Daniel P
    Commented Feb 19, 2018 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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