19
$\begingroup$

You are asked to arrange 42 identical cubes such that exactly three of each cube's faces completely overlap another cube's face each.

Is this task possible? If not, why not?

$\endgroup$
18
$\begingroup$

The task is

possible. Here's one solution:

Layer 1:


Layer 2:

$\endgroup$
5
  • 2
    $\begingroup$ Nice. Could be turned into a single structure by extending it 1 square horizontally on each side $\endgroup$ – astralfenix Sep 28 '16 at 15:07
  • 2
    $\begingroup$ I wonder if you could do it with fewer cubes (aside from trivial cases). $\endgroup$ – Matsmath Sep 28 '16 at 15:09
  • 1
    $\begingroup$ @Matsmath: To be more specific - what is the smallest number of cubes that is not a multiple of 4 with which you can build a structure such that every cube has exactly 3 neighbours. From McFry's answer we know a 34 cube solution. $\endgroup$ – Jaap Scherphuis Sep 28 '16 at 15:28
  • 1
    $\begingroup$ And after all the hours I spent trying to prove that it's impossible!! Damn you, and +1 :-D $\endgroup$ – Rand al'Thor Sep 28 '16 at 16:34
  • $\begingroup$ I will now go cry in a corner. $\endgroup$ – greenturtle3141 Sep 29 '16 at 13:41
2
$\begingroup$

Partial Answer:

No. 'Tis impossible.

I will try to expand my answer eventually.

Partial Proof:

We use proof by contradiction. We assume such a structure of $42$ cubes exists in a normal gridlike arrangement such that each cube touches three others.
We use the extremal principal. Consider the top-most layer of cubes. There are no cubes above said layer.

I will take cases.

Case 1:

In this first case, let's say each cube of the top-layer has a cube under it. Considering only the top-layer, each cube must touch two others. This implies that the top layer must be a single closed loop of cubes.
After said loop of cubes, we consider the second layer. It already consists of all the cubes immediately under the top layer. Since each cube now in this structure is adjacent to two cubes in its plane, and the cube above/under, each cube touches three others. The resulting structure has two layers.
This tells us that the number of cubes must be divisible by two. Additionally, the closed loop must have an even number of cubes by parity. The total number of cubes must be then divisible by 4. Oh wait...

Case 2 partially thought out:

What if there is a cube in the top layer that touches three others in that layer? Note that there must be an even number of such cubes. We can see why: Consider just one lone cube that touches three in the same layer.
SNAAAAKE
As we can see, two of the ends extruding from the odd cube out have successfully finished Tron: Valentine's Day Edition and met to form a closed loop. However, the other end is lost and can't form a closed loop without causing another cube to have three neighbors.
From what we have seen, it is not far fetched to assert that if there are $n$ cubes with three neighbors in the top layer, then the top layer must have $\frac{n}{2}$ closed loops. Note that I consider a $2\times2$ square a closed loop. It's a very small one at that.
Now we can consider the second layer! It consists of all cubes under that of the first layer, EXCEPT those who already have three neighbors. I have no idea how to prove that after adding in a hypothetical resolution to those cubes that do not have three neighbors, that the resulting structure has a number of cubes divisible by 4 or more than 42.

$\endgroup$
2
  • $\begingroup$ "if there are n cubes with three neighbors in the top layer, then the top layer must have n/2 closed loops" ... this isn't true. In your picture, if the 2 blue squares at the top right had 3 neighbors, forming a loop at the top right, and there was a loop at the bottom left as well, then the result would be 3 loops with 4 cubes which have 3 neighbors $\endgroup$ – astralfenix Sep 28 '16 at 8:21
  • $\begingroup$ Using Euler's formula $V-E+F=2$ where $V=n$ is the number of cubes with 3 neighbours, $E=3n/2$ is the number of connections between them, you get that $F=2+n/2$. Exclude the infinite outside area, then there are $1+n/2$ closed faces, so @greenturtle3141 was off by one. $\endgroup$ – Jaap Scherphuis Sep 28 '16 at 8:43
1
$\begingroup$

I don't think it is possible.

To get a cube overlapping 3 faces we could arrange it into a $21\times2\times1$ cuboid. Basically 2d

All the cubes would overlap exactly 3 faces except the corners which overlap 2

So to fix that we make it a $3\times2\times7$ cuboid. Now it is 3d.

The corners now overlap 3 faces but the other cubes overlap up to 5

Hence it is impossible as it doesn't work in 2 or 3 dimensions, which are the only options

It is possible to have 38 cubes overlap 3 and the remaining 4 overlapping 2 but that is the closest you can get it

I have assumed it must be cuboid as any other shape would result in a cuboid on the outside overlapping only 1 face

$\endgroup$
13
  • $\begingroup$ Beastly, this seems to make assumptions about how regular the arrangement is, and I don't see what licenses those assumptions. @randal'thor, you do realise you've just discouraged everyone else from upvoting this answer, right? $\endgroup$ – Gareth McCaughan Sep 27 '16 at 11:42
  • $\begingroup$ He never said it had to be a cubiod though $\endgroup$ – Joe Derksen Sep 27 '16 at 11:43
  • $\begingroup$ @Marius I took the screenshot while the question was answered 6 minutes ago :P the more sixes the better haha: i.stack.imgur.com/OPFno.png $\endgroup$ – Ivo Beckers Sep 27 '16 at 11:44
  • $\begingroup$ @GarethMcCaughan I'll add my reasoning $\endgroup$ – Beastly Gerbil Sep 27 '16 at 11:45
  • 5
    $\begingroup$ Take a 3x3x2 block. Remove the two cubes in the centre. Now the corner cubes are adjacent to 3 other cubes each, one on each axis; and the ones in the middle are each adjacent to two corners and one other middle cube. Therefore, you can get 3 adjacencies everywhere without the arrangement being a cuboid. (This arrangement can be generalized somewhat but it won't do 42 cubes.) $\endgroup$ – Gareth McCaughan Sep 27 '16 at 11:58

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.