3
$\begingroup$

An $S$-tileset is a collection of $n$ oriented tiles, where no two tiles have the same size, each tile is one unit thick, and its non-zero-integer length and width add up to $n+1$. (So, an $S$-tileset has $n$ tiles, of sizes $1\times n, 2\times{n-1}, ... n\times1$.) You can make a tower of tiles by stacking up layers of tiles; tiles in a layer adjoin; rotation of tiles is not allowed; you don't have to use all tiles. Overhang is not allowed: all the area of each layer must be supported by an area of the layer below.

How high is the tallest tower that can be made with one $S$-tileset? [If you can write the answer in terms of $n$, great; else exhibit solutions for $n\in\{6,9,12\}$]

How high can it be if given two $S$-tilesets?

How high is the tallest tower that can be made with one $S$-tileset if you break the rules and rotate some tiles?

Improve this question
$\endgroup$
6
  • $\begingroup$ A good puzzle. I would delete the last two paragraphs. I found some simple answers to the first problem that failed, so I think we should concentrate on that. If/when we have that, we can think about the others. $\endgroup$
    – Ross Millikan
    Aug 10, 2014 at 3:17
  • $\begingroup$ @RossMillikan, fair enough – I was concerned even the first question by itself might be thought too broad $\endgroup$
    – James Waldby - jwpat7
    Aug 10, 2014 at 3:30
  • $\begingroup$ Do not rules (that you can't rotate and overhang) force us to put exactly i-th tile on (i-1)-th? Can you give two different examples of the tower from two S-tiles? $\endgroup$
    – klm123
    Aug 10, 2014 at 5:41
  • $\begingroup$ Or 1 is the height of the tiles? (I thought 1,2,...n would be hight, and n,..,2,1 would be length). and you must always put several tiles together to put another tile on it? And basically question is how many layers of the tiles you can create? $\endgroup$
    – klm123
    Aug 10, 2014 at 5:48
  • 1
    $\begingroup$ @klm123: you can always put all the tiles on the table. For $S=6$ you can put the $1 \times 6$ and $2 \times 5$ next to each other and make an $L$ with $6 \times 1$ and $2 \times5$. Either the $3 \times 4$ or $4 \times 3$ will fit on top. $\endgroup$
    – Ross Millikan
    Aug 10, 2014 at 13:58

2 Answers 2

Reset to default
5
$\begingroup$

I can only get 3 deep with each of 6,9, and 12 blocks. The 12 block solution is 'almost' 4 deep but not quite.

enter image description here

Regarding KSab's answer - I can confirm for n=13 I can get his minimum of 4 deep. enter image description here

...and looking a little further I can get 7 layers for n=39. Apart from the 2nd layer, the overlaps are fairly 'efficient'.

enter image description here

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

I thought I might as well mention what results I have gotten from just a little thinking, sketching, and coding. First a very obvious upper bound for the number of layers is $\frac{n+1}{2}$ because every layer up to the second to highest must have at least two tiles in it. I am sure this can be significantly improved but its not trivial, as you can place two tiles on another two (for example a 1x6 and a 5x2 on a 4x3 and a 2x5).

As for a lower bound, I considered the case in which you start with 1xn on the highest level, and simply vertically tile the rest of the tiles in order (moving to a lower level when able). For example for n=8, you have the 1x8 on the top, the 2x7 and 3x6 (giving 4 extra spaces of verticle room), and the 4x5, 5x4, 6x3, 7x2 (and optionally the 8x1) on the bottom row. Note how since they are done in order, horizontal space is a non-issue. Though it isn't hard to calculate, I don't know of anyway to turn this into a formula and from looking through some values it seems relatively difficult to predict.

In any case this is what we get with these bounds:

n

3: 1 <= L <= 2

4: 2 <= L <= 2

5: 2 <= L <= 3

6: 2 <= L <= 3

7: 2 <= L <= 4

8: 3 <= L <= 4

9: 3 <= L <= 5

10: 3 <= L <= 5

11: 3 <= L <= 6

12: 3 <= L <= 6

13: 4 <= L <= 7

14: 4 <= L <= 7

15: 4 <= L <= 8

I think I will try lowering the upper bound, as it seems like it should be possible to do a fair bit more than the very simple formula I have now.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I get your minimum for n=9,12,13 but for n=6 I get your maximum. $\endgroup$
    – Penguino
    Aug 13, 2014 at 2:54
  • $\begingroup$ @Penguino Oh I didn't see that, nice catch. Though I don't really doubt the numbers you list in your answer (I messed around myself and can't see how you could get any higher) I would be interested to see if it was possible to prove that those were the maximums. I suppose I could try and write a program to brute force the combinations but I feel like it would be hard to get it to run in any reasonable amount of time for the bigger numbers. $\endgroup$
    – KSab
    Aug 13, 2014 at 3:27
  • $\begingroup$ I have tried tightening the limits between min and max by looking at factors like 'minimum-area-if-layer-n'. Initially it looked hopeful, but for moderate n it seems to get complicated quickly. Brute force will be very slow, and won't provide any 'feeling' for how the limit is reached. $\endgroup$
    – Penguino
    Aug 13, 2014 at 4:23

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.