💾 Archived View for jdcard.com › bp.gmi captured on 2023-09-28 at 15:33:24. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
👴 jdcard
I sat watching a construction crew digging up a section of roadway and began thinking about the various bits of infrastructure that may be buried under there. Pipes for water, natural gas, storm drains, and sanitary sewers. Cable for electric power, telephones, and cable TV. Possibly even tunnels for a subway or underground parking.
Any given cubic meter of earth might have multiple pipes, cables, and other stuctures routed through it, possibly crisscrossing in several different directions. Before they start digging they have to know what's under there. Each utility company maintains records of the size, location, and direction of each pipe or cable or other stucture they've buried.
I began to wonder whether some of the most dense portions of the city might have trouble keeping all these various components safely routed so as not to interfere with each other. How many pipes can you install within any given space? Wandering minds may stray….
I'm guessing that engineering students encounter problems like this early in their studies, and probably develop mathematical tools to help them derive optimal answers. I don't have a math or engineering background, so for me this is an interesting puzzle that I'll try to solve by generating "typewriter diagrams" (drawings such as one might produce using only an old mechanical typewriter).
Imagine you have a supply of blocks, each one a cube with edges 1 centimeter long, and a supply of pipes, each being 10 centimeters long and having an outside diameter of 1 centimeter. The sizes aren't important except to specify that the pipe diameter is the same as the edge of the cube. I selected this size because it helped me visualize the problem: I can imagine sitting at the kitchen table with a stack of sugar cubes and a box full of soda straws.
Stack the blocks and pipes together to build a larger cube of 10 centimeters along each edge. Insert as many pipes as possible into each face of the larger cube. How many pipes can be inserted into each face?
An optimal solution for a single face might look like this:
10 ::::::::::
9 ::::::::::
8 :O:O:O:O::
7 ::::::::::
6 :O:O:O:O::
5 ::::::::::
4 :O:O:O:O::
3 ::::::::::
2 :O:O:O:O::
1 ::::::::::
1234567890
We can get a maximum of 16 pipes this way.
By rotating the first and third tiers containing pipes by 90 degrees (imagining a Rubik's cube now) we'll have something like this:
Front face Right face
10 :::::::::: ::::::::::
9 :::::::::: ::::::::::
8 :::::::::: :O:O:O:O::
7 :::::::::: ::::::::::
6 :O:O:O:O:: ::::::::::
5 :::::::::: ::::::::::
4 :::::::::: :O:O:O:O::
3 :::::::::: ::::::::::
2 :O:O:O:O:: ::::::::::
1 :::::::::: ::::::::::
1234567890 1234567890
We've still got 16 pipes included in the cube.
That gives us pipes running from the front to the back of the cube, and from the left side to the right side. Now, how do we modify this to incorporate pipes running from top to bottom?
Notice that no matter which face you look at there are exactly 16 spaces where a pipe could fit, in a 4x4 grid. If we number the edges of the large cube from 1 to 10 then we'll notice that the pipes can only be in even-numbered spaces.
1234567890
10 +--------+ 10
9 / /| 9
8 / / | 8
7 / / | 7
6 / / | 6
5 / / | 5
4 / / | 4
3 / / | 3
2 / / | 2
:::::::::: 10 +--------+ + 10 Back
:::::::::: 9 | | / 9
:O:O:O:O:: 8 | | / 8
:::::::::: 7 | | / 7
:O:O:O:O:: 6 | | / 6
:::::::::: 5 | | / 5 Center
:O:O:O:O:: 4 | | / 4
:::::::::: 3 | | / 3
:O:O:O:O:: 2 | |/ 2
:::::::::: 1 +--------+ 1 Front
1234567890 1234567890
Before tackling the details of the problem let's look at simpler versions of it. Let's start with a 3x3x3 cube.
123
+-+
/ /|
::: 3 +-+ + 3 Back
:O: 2 |O|/ 2 Center
::: 1 +-+ 1 Front
123 123
This is the simplest version of the blocks and pipes problem. There is exactly one even-numbered place to put a pipe. When we extend our grid into three-dimensional space we'll use three numbers to designate each position where a block could be.
Back
Center 3 :::
Front 3 ::: 2 :::
3 ::: 2 :@: 1 :::
2 ::: 1 ::: 123
1 ::: 123
123
The address of the block at the center of our 3x3x3 cube -- shown above as "@" -- is calculated like this: starting at the left bottom front corner of the cube we count first from left to right: 1 - 2; then from bottom to top: 1 - 2; finally from front to back: 1 - 2; giving us an address for that location of "2,2,2". No matter whether we insert the pipe going front-to-back, left-to-right, or bottom-to-top, the pipe will pass through that space. The path that a pipe from front to back would take through the cube would be described as ((2,2,1), (2,2,2), (2,2,3)).
A 3x3x3 cube with one pipe doesn't help much to answer our question: how many pipes can be placed in each face of a 10x10x10 cube? Let's expand this to a 5x5x5 cube. Our cubes all have an odd number of blocks for each side because each pipe must be protected on each side by at least one block.
12345
+---+
/ /|
/ / |
/ / |
::::: 5 +---+ + 5 Back
:O:O: 4 |O O| / 4
::::: 3 | | / 3 Center
:O:O: 2 |O O|/ 2
::::: 1 +---+ 1 Front
12345 12345
Now we have space for 4 pipes through the cube. Drawn on the front face of the cube they are at (2,2), (2,4), (4,2), and (4,4). The paths they take from the front face to the back face are described as:
Now rotate the top layer of pipes 90 degrees so they run left to right rather than front to back.
12345
+---+
/ /|
/ /O|
Front Right / / |
::::: ::::: 5 +---+O + 5 Back
::::: :O:O: 4 | | / 4
::::: ::::: 3 | | / 3 Center
:O:O: ::::: 2 |O O|/ 2
::::: ::::: 1 +---+ 1 Front
12345 12345 12345
Now there are pipes running front-to-back and left-to-right; there are still 4 pipes. Here are the paths these four pipes take:
Can we modify this so we have at least one pipe running bottom-to-top?
First let's trim out some unnecessary detail. In both sets of paths you can see that the pipes pass through all 8 of the even-numbered locations in the center of the cube: (2,2,2), (2,2,4), (4,2,2), (4,2,4), (2,4,2), (2,4,4), (4,4,2), and (4,4,4). We can consider these addresses as control nodes or as critical points in the path. It is safe to ignore all the addresses in the path that contain an odd number because the pipe passes through that point only incidentally. Now let's map out just these control nodes.
12345 Key: - left-to-right pipe
+---+ / front-to-back pipe
/ /|
/ /O|
/ / | -2,4,4- -4,4,4-
5 +---+O + 5 Back -2,4,2- -4,4,2-
4 | | / 4
3 | | / 3 Center /2,2,4/ /4,2,4/
2 |O O|/ 2 /2,2,2/ /4,2,2/
1 +---+ 1 Front
12345
Obviously if all the even-numbered spaces are being used we'll have to remove at least one pipe. Let's take out the one that runs through (2,2,2) and (2,2,4), freeing up two of the control nodes. Now we'll place that pipe at (2,2,2) and run it up to (2,4,2)... oops! There is already a pipe there, so we also have to take out the one from (2,4,2) to (4,4,2). Now we have 4 of the 8 control nodes free: (2,2,2), (2,2,4), (2,4,2), and (4,4,2). Okay, now we can insert our bottom-to-top pipe from (2,2,2) to (2,4,2). This also leaves two of the control nodes empty: (2,2,4) and (4,4,2), because there is no way to connect those two nodes with a pipe.
12345 Key: - left-to-right pipe
+---+ / front-to-back pipe
/ /| | bottom-to-top pipe
/ /O|
/O / | -2,4,4- -4,4,4-
5 +---+ + 5 Back |2,4,2| 4,4,2
4 | | / 4
3 | | / 3 Center 2,2,4 /4,2,4/
2 | O|/ 2 |2,2,2| /4,2,2/
1 +---+ 1 Front
12345
Success! Now each face of the cube has a pipe. There are 3 pipes total. Their paths are (now using the simplified even-numbers-only notation):
Now let's try a 7x7x7 cube. At the left of the drawing is the front face of the cube showing the maximum number of pipes (9) that can be placed in a 7x7 grid.
The control nodes create a 3x3x3 cube inside the 7x7x7 outer space, making a total of 27 even-numbered control nodes: [(2,2,2), (2,2,4), (2,2,6), (2,4,2), (2,4,4), (2,4,6), (2,6,2), (2,6,4), (2,6,6), (4,2,2), (4,2,4), (4,2,6), (4,4,2), (4,4,4), (4,4,6), (4,6,2), (4,6,4), (4,6,6), (6.2.2), (6.2.4), (6.2.6), (6,4,2), (6,4,4), (6,4,6), (6,6,2), (6,6,4), (6,6,6)], which are mapped out on the right side of the diagram.
+-----+
/ o/| /2,6,6/ /4,6,6/ |6,6,6|
/ / | /2,6,4/ /4,6,4/ 6,6,4
/ / | /2,6,2/ /4,6,2/ |6,6,2|
/ / |
/ O/ | 2,4,6 4,4,6 |6,4,6|
::::::: 7 +-----+ O + 7 Back -2,4,4- -4,4,4- -6,4,4-
:O:O:O: 6 |O o | / 6 2,4,2 4,4,2 |6,4,2|
::::::: 5 | | o/ 5
:O:O:O: 4 | | / 4 Center 2,2,6 4,2,6 |6,2,6|
::::::: 3 | | / 3 -2,2,4- -4,2,4- -6,2,4-
:O:O:O: 2 | |/ 2 2,2,2 4,2,2 |6,2,2|
::::::: 1 +-----+ 1 Front
1234567 1234567
I initially thought I could safely place three pipes into the cube without risking internal collisions. This diagram shows where I placed them, using a capital letter "O" to represent their locations within the front face (for a front-to-back pipe), the right face (for a left-to-right pipe) and the top face (for a bottom-to-top pipe).
Front Right Top
::::::: ::::::: 7 ::::::: .......
:O:o::: ::::::: 6 :::::o: .F.F.T.
::::::: ::::::: 5 ::::::: .......
::::::: :::O::: 4 ::::::: ...R...
::::::: ::::::: 3 ::::::: .......
::::::: :::o::: 2 :::::O: ...R.T.
::::::: ::::::: 1 ::::::: .......
1234567 1234567 1234567 1234567
Here are the paths of those inital 3 pipes.
Seeing their positions in the mapping of the control nodes it became obvious that there were three additional paths possible, each of them parallel to one of the first lines. The pipes indicated with a lower-case letter "o" indicate the placement of a second set of pipes after successfuly mapping out the control nodes of the first set. These control node paths are:
This gives us two pipes on each face of the cube, and leaves 9 unused control nodes that cannot be connected to create paths for additional pipes.
How many pipes can be placed in each face of a 10x10x10 cube? Based on the information we've gathered so far, I will predict the number is 3. Can we derive a formula that calculates that number?
1234567890 2,8,8 4,8,8 |6,8,8| 8,8,8
O - pipe 1 10 +--------+ 10 2,8,6 4,8,6, |6,8,6| 8,8,6
o - pipe 2 9 / /| 9 2,8,4 4,8,4 |6,8,4| 8,8,4
* - pipe 3 8 / o / | 8 -2,8,2- -4,8,2- -6,8,2- -8,8,2-
7 / / | 7
6 / O / | 6 2,6,8 4,6,8 |6,6,8| 8,6,8
5 / / | 5 2,6,6 4,6,6 |6.6.6| 8,6,6
4 / * / | 4 2,6,4 4,6,4 |6,6,4| 8,6,4
3 / / | 3 -2,6,2- -4,6,2- -6,6,2- -8,6,2-
2 / / | 2
:::::::::: 10 +--------+ + 10 Back 2,4,8 4,4,8 |6,4,8| 8,4,8
:::::::::: 9 | | / 9 2,4,6 4,4,6 |6,4,6| 8,4,6
:O:O:O:O:: 8 | |* / 8 2,4,4 4,4,4 |6,4,4| 8,4,4
:::::::::: 7 | | / 7 -2,4,2- -4,4,2- -6,4,2- -8,4,2-
:O:O:O:O:: 6 | |o / 6
:::::::::: 5 | | / 5 Center /2,2,8/ /4,2,8/ |6,2,8| /8,2,8/
:O:O:O:O:: 4 | |O / 4 /2,2,6/ /4,2,6/ |6,2,6| /8,2,6/
:::::::::: 3 | | / 3 /2,2,4/ /4,2,4/ |6,2,4| /8,2,4/
:O:O:O:O:: 2 |O o * |/ 2 /2,2,2/ /4,2,2/ 6,2,2 /8,2,2/
:::::::::: 1 +--------+ 1 Front
1234567890 1234567890
Front Right Top
:::::::::: :::::::::: 10 :::::::::: ..........
:::::::::: :::::::::: 9 :::::::::: ..........
:::::::::: :*:::::::: 8 :::::o:::: .R...T....
:::::::::: :::::::::: 7 :::::::::: ..........
:::::::::: :o:::::::: 6 :::::O:::: .R...T....
:::::::::: :::::::::: 5 :::::::::: ..........
:::::::::: :O:::::::: 4 :::::*:::: .R...T....
:::::::::: :::::::::: 3 :::::::::: ..........
:O:o:::*:: :::::::::: 2 :::::::::: .F.F...F..
:::::::::: :::::::::: 1 :::::::::: ..........
1234567890 1234567890 1234567890 1234567890
If the grid size is an even number, subtract 1 so we're working with an odd-numbered grid. (10-1=9)
Divide the grid size by 2 (9/2=4.5) and drop the remainder to get an integer result (4). The maximum number of pipes that can be placed in each face is one less than this result (4-1=3).
No sugar cubes or soda straws were actually used to solve this. However, I'm now thinking that it probably would have been much faster to do it that way than it was to type out all these diagrams and explanations 😅.
⁂
In case you want to tinker with the problem yourself:
1234567890 2,8,8 4,8,8 6,8,8 8,8,8
10 +--------+ 10 2,8,6 4,8,6, 6,8,6 8,8,6
9 / /| 9 2,8,4 4,8,4 6,8,4 8,8,4
8 / / | 8 2,8,2 4,8,2 6,8,2 8,8,2
7 / / | 7
6 / / | 6 2,6,8 4,6,8 6,6,8 8,6,8
5 / / | 5 2,6,6 4,6,6 6.6.6 8,6,6
4 / / | 4 2,6,4 4,6,4 6,6,4 8,6,4
3 / / | 3 2,6,2 4,6,2 6,6,2 8,6,2
2 / / | 2
:::::::::: 10 +--------+ + 10 Back 2,4,8 4,4,8 6,4,8 8,4,8
:::::::::: 9 | | / 9 2,4,6 4,4,6 6,4,6 8,4,6
:O:O:O:O:: 8 | | / 8 2,4,4 4,4,4 6,4,4 8,4,4
:::::::::: 7 | | / 7 2,4,2 4,4,2 6,4,2 8,4,2
:O:O:O:O:: 6 | | / 6
:::::::::: 5 | | / 5 Center 2,2,8 4,2,8 6,2,8 8,2,8
:O:O:O:O:: 4 | | / 4 2,2,6 4,2,6 6,2,6 8,2,6
:::::::::: 3 | | / 3 2,2,4 4,2,4 6,2,4 8,2,4
:O:O:O:O:: 2 | |/ 2 2,2,2 4,2,2 6,2,2 8,2,2
:::::::::: 1 +--------+ 1 Front
1234567890 1234567890
Front Right Top
:::::::::: :::::::::: 10 :::::::::: ..........
:::::::::: :::::::::: 9 :::::::::: ..........
:::::::::: :::::::::: 8 :::::::::: ..........
:::::::::: :::::::::: 7 :::::::::: ..........
:::::::::: :::::::::: 6 :::::::::: ..........
:::::::::: :::::::::: 5 :::::::::: ..........
:::::::::: :::::::::: 4 :::::::::: ..........
:::::::::: :::::::::: 3 :::::::::: ..........
:::::::::: :::::::::: 2 :::::::::: ..........
:::::::::: :::::::::: 1 :::::::::: ..........
1234567890 1234567890 1234567890 1234567890
⁂
©2023 🅭🅯🄏🄎 Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)
⋯