Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.
Most efficient way to place rooms in a compound whilst following certain criteriaedit
I'm trying to design a large underground compound in Minecraft that would use a modular, cell-based room/corridor system.
The piece to be tiled is a 15x15-cell area.
Each cell can be either a room or a corridor, with the exception of the center cell, which is a staircase.
Rooms have only one entrance/exit.
I'm trying to design the 15x15-cell tiled piece to fit the following criteria:
The center cells must be connected by a straight line of corridors.
The corridors must not have any "dead ends" - each path of corridors must be followable from one center cell to another without the need to turn around.
Rooms must connect to at least one corridor. Connecting diagonally doesn't count.
The design must have 90-degree rotational symmetry. Thus, it must be able to be split into identical quadrants that are rotated in 90-degree increments.
There should be as many rooms as possible.
When I tried to work out a solution (with a bit of help from Freenode's ##math channel), I got this. When tiled, it looks like this. Black pixels are rooms, white pixels are tiles. The staircases are the blue pixels. I count 124/225 rooms - using a total area of 55.111%.
Can anyone help me with figuring out the most efficient solution to this situation?
If edge conditions aren't important, it might be easier to think about things if instead of having the staircase in the center, you think about the staircase and straight-line corridors forming a grid, with a 14x14 square between. (Made up of four 7x7 blocks still with 90 degree rotational symmetry in the center.) This way you don't have to worry about connecting the edges, as any corridor that ends on the edge will automatically connect with the stair corridor grid. Past that, I'm not sure what you consider to be rooms versus corridors, or what additional limitations you have. (e.g. what's keeping you from carving out the space entirely, or almost entirely.) -- 71.35.111.68 (talk) 04:44, 18 May 2013 (UTC)[reply]
The space in question is a square 15 cells wide. Each cell is the size of one room/corridor. The drawing is not that of a single 15x15-block room, but of a 15x15-chunk area (16 times larger than the former). The most obvious and most efficient design would be to arrange the rooms in aisles like this, but that doesn't follow the rule of the design having rotational symmetry. Rotating it to fit this would cause dead ends to form. If one were to remove one row from each quadrant like this, it is less efficient than the manner linked above. Hmmwhatsthisdo (talk) 06:05, 18 May 2013 (UTC)[reply]
How about this variant on the design with 132 rooms out of 225? Dmcq (talk) 15:08, 18 May 2013 (UTC)[reply]
sin(pi/6)=1/2. Are there any other rational multiples of pi, less than pi/2, with a rational value of their sine? If not, how can it be proved? 86.139.121.71 (talk) 14:23, 18 May 2013 (UTC)[reply]
Consider a primitive nth root of unityz=e2kπi/n. (Hence k and n are relatively prime.) If the real or imaginary part of z is rational, then z belongs to the field Q[i] or, at worst, a quadratic extension of Q[i] (i.e. an extension of degree 2). This implies that the degree of z over Q must be 1, 2 or 4. Thus the cyclotomic polynomial Φn, which is irreducible over Q, and hence is the minimal polynomial of z, must have degree 1, 2 or 4. Therefore φ(n) must be 1, 2 or 4, where φ is the Euler indicator function. It can be checked that n must therefore be among 1, 2, 3, 4, 5, 6, 8, 10, 12. I haven't checked these, but this means you only need to check multiples of 2π/n for these values of n (not necessarily in the first quadrant). 96.46.198.58 (talk) 15:15, 18 May 2013 (UTC)[reply]
Addendum: Among these cases, only n=5 and n=10 present any difficulty. It is easy to see, after reduction to the first quadrant, that it is enough to check the sines and cosines of 72° and 144°. Let z be a primitive fifth root of unity. The cosine c of the corresponding angle is given by 2c = z + 1/z. From the equation Φ5(z) = z4 + z3 + z2 + z + 1 = 0, we obtain 4c2 + 2c - 1 = 0. Since the discriminant of this equation, 20, is not a perfect square, c cannot be rational. The sine s of the angle satisfies s2 = 1 - c2 = (2c + 3)/4. Since c is irrational it follows that s2, and hence s, is irrational. Therefore the example you gave that occurs for n= 12 (and/or its divisors) is the only one (other than the trivial cases of 0° and 90°). 96.46.198.58 (talk) 16:20, 18 May 2013 (UTC)[reply]
There is a proof in this article that the rational cosine of a rational mutiple of π can only be 0, +/-1 or +/-½. It uses the angle doubling formula
to show that for α with rational cosine, doubling α squares the denominator of 2 cos α in its lowest terms. If α is a rational multiple of π then the sequence of doubled angles 2k α mod π is eventually periodic so sequence of denominators of 2 cos (2k α) takes a finite number of distinct values, and we have a contradiction unless 2 cos α is an integer. Argument is easily extended to sines. Gandalf61 (talk) 08:50, 19 May 2013 (UTC)[reply]
Thank you very much for the nice, elementary proof. I enjoyed it. The theorem at the end of that paper also provides an improved and streamlined version of the one I gave above, in which the possibility that φ(n) = 4 is eliminated for theoretical reasons (albeit for cosines, not for sines - but that is easily remedied). That saves time and is quite satisfying. 96.46.198.58 (talk) 15:21, 19 May 2013 (UTC)[reply]
How does x^2 + x + 3 relate to area in real life?edit
I am never afraid to ask a "dumb" question.
I have to admit that I can see the point of a second order polynomial such as f(x)=x^2+x+3 as simply representing a continuous sequence of numbers or a real life curve that a machine could cut but I have trouble understanding as to how it may relate to actual real life area.
There is the always the mention of crop yields in ancient times to illustrate this but I have never found a satisfactory simple explanation about it, can anyone help me on this one?
I'm not sure I follow. Perhaps if you gave an example of something that you consider to be real life and something which you consider as not real life it would help thanks. Dmcq (talk) 15:25, 18 May 2013 (UTC)[reply]
Well the area of a field can be x^2 i.e. 10m^2 but how can you have an area of 10m^2 + 10m +3 ? Ap-uk (talk) 15:57, 18 May 2013 (UTC)[reply]
Here's an example: A field is twice as long as its width. The field can be farmed up to 1m from its edges (i.e. there is a 1m uncultivated border). Express this algebraically.
If the width is x, the length is 2x, then the area that can be cultivated is
(x - 2) (2x - 2) = 2x^2 -6x + 4
x is in metres and the formula calculates the area in square metres. To confirm it plug in some numbers. E.g. if x = 10 it gives 144. So a field 10m x 20m with 1m borders had an area of 144m^2 under cultivation.--JohnBlackburnewordsdeeds 16:10, 18 May 2013 (UTC)[reply]
Thank you :) Ap-uk (talk) 17:03, 18 May 2013 (UTC)[reply]
What is meaning of Nm and how does it relate to pound/feet and/or inc/pounds? — Preceding unsigned comment added by Romanodizoppola (talk • contribs) 18:21, 18 May 2013 (UTC)[reply]
