Brain-Teaser 150: Paving the way
From The Sunday Times, 23rd February 1964 [link]
I have eight paving stones whose dimensions are an exact number of inches. Their areas are 504, 420, 324, 306, 270, 130, 117 and 112 square inches. Four of these are red and four green. There should be a ninth stone coloured yellow and square so that all nine stones can be fitted together to form a square in such a way that the red stones completely enclose the other five and the green stones completely enclose the yellow one.
What are the dimensions of the red stones?
[teaser150]
Frits and 
GeoffR, 
Hugh+Casement and 
John Crabtree, and 
S2T2 
Jim Randell 8:03 am on 10 July 2022 Permalink |
The tiles that are mentioned have a total area of 2183.
If the missing central tile has an area of x², and the entire collection has an area of y² then we have:
So we can calculate possible values for x and y by examining the divisors of 2183.
The Python program find values for x and y, and then chooses 4 green tiles, along with the x by x yellow square, which can fit together to form a square. And then checks that this square, along with the the remaining (green) tiles can fit together to form a y by y square.
We use the rectpack.py module to fit the tiles into squares.
The program runs in 169ms.
Run: [ @replit ]
from enigma import (divisors_pairs, div, subsets, is_square, cproduct, printf) import rectpack # areas of tiles we are given areas = {504, 420, 324, 306, 270, 130, 117, 112} # record possible tiles dps = dict((x, list(divisors_pairs(x))) for x in areas) # select tiles by area <x>, with max dimension not exceeding <m> tiles = lambda x, m: ((a, b) for (a, b) in dps[x] if not (b > m)) # pack rectangles <rs> and an <s> by <s> square into a <t> by <t> square def pack(rs, s, t): # make the list of rectangles rs_ = [(s, s)] rs_.extend(rs) # pack them into a t by t square for ps in rectpack.pack(t, t, rs_): # check the square is not on the edge if not any( w == h == s and x > 0 and y > 0 and x + w < t and y + h < t for (x, y, w, h) in ps ): continue return ps # we only need one packing # consider divisors of the total area for (a, b) in divisors_pairs(sum(areas)): # calculate x and y (x, y) = (div(b - a, 2), div(a + b, 2)) if x is None or y is None or y < x + 4: continue # choose 4 green tiles to go around a central x by x square for green in subsets(areas, size=4): z = is_square(x * x + sum(green)) if z is None: continue # consider dimensions of green tiles for gs in cproduct(tiles(x, z) for x in green): # pack them into a z by z square ps1 = pack(gs, x, z) if ps1 is None: continue # consider dimensions of red tiles red = areas.difference(green) for rs in cproduct(tiles(x, y) for x in red): # pack them into a y by y square ps2 = pack(rs, z, y) if ps2 is None: continue # output packings printf("red {red} around {z} x {z} green in {y} x {y}\n-> {ps2}") printf("green {green} around {x} x {x} yellow in {z} x {z}\n-> {ps1}") printf()Solution: The dimensions of the red stones (in inches) are: 3×39, 6×45, 9×36, 12×42.
Here is a diagram of one possible layout:
LikeLike
Frits 1:01 pm on 10 July 2022 Permalink |
@Jim, it is not stated that the yellow and green tiles form a square.
LikeLike
Jim Randell 1:11 pm on 10 July 2022 Permalink |
@Frits: Is there a way the red stones can enclose the green ones without forming a square?
LikeLike
Jim Randell 1:14 pm on 10 July 2022 Permalink |
I suppose it could be a non-square rectangle. But luckily it is possible to do it with a square.
LikeLike
Frits 1:18 pm on 10 July 2022 Permalink |
So there might be another solution…
LikeLike
Jim Randell 1:26 pm on 10 July 2022 Permalink |
I made some tweaks to my program, and it didn’t find any solutions with a non-square rectangle. But I’ll have a closer look.
LikeLike
Jim Randell 2:53 pm on 10 July 2022 Permalink |
This is my program adapted to consider packing the green and yellow tiles into a (possibly non-square) rectangle.
It doesn’t find any additional solutions.
Run: [ @replit ]
from enigma import (divisors_pairs, div, subsets, cproduct, printf) import rectpack # areas of tiles we are given areas = {504, 420, 324, 306, 270, 130, 117, 112} # record possible tiles dps = dict((x, list(divisors_pairs(x))) for x in areas) # select tiles by area <x>, with max dimension not exceeding <m> tiles = lambda x, m: ((a, b) for (a, b) in dps[x] if not(b > m)) # pack rectangles <rs> and rectangle <s> into a bounding rectangle <t> def pack(rs, s, t): (a, b) = t # make the list of rectangles rs_ = [s] rs_.extend(rs) # pack them into a the rectangle for ps in rectpack.pack(t[0], t[1], rs_): # check that s is not on the edge if not any( x > 0 and y > 0 and x + w < a and y + h < b and {w, h} == set(s) for (x, y, w, h) in ps ): continue return ps # we only need one packing # consider divisors of the total area for (a, b) in divisors_pairs(sum(areas)): # calculate x and y (x, y) = (div(b - a, 2), div(a + b, 2)) if x is None or y is None or y < x + 4: continue # choose 4 green tiles to go around the central x by x square for green in subsets(areas, size=4): for (a, b) in divisors_pairs(x * x + sum(green)): if a < x + 2 or y < b + 2: continue # consider dimensions of green tiles for gs in cproduct(tiles(x, b) for x in green): # pack them into an a by b rectangle ps1 = pack(gs, (x, x), (a, b)) if ps1 is None: continue # consider dimensions of red tiles red = areas.difference(green) for rs in cproduct(tiles(x, y) for x in red): # pack them into a y by y square ps2 = pack(rs, (a, b), (y, y)) if ps2: # output packings printf("red {red} around {a} x {b} green in {y} x {y}\n-> {ps2}") printf("green {green} around {x} x {x} yellow in {a} x {b}\n-> {ps1}") printf()LikeLike
Frits 5:02 pm on 10 July 2022 Permalink |
One piece of logic is not coded, it turns out it is not needed.
from enigma import divisors_pairs from itertools import product # find three other red pieces which can form the outer ring def check(a, b, d): # combinations of length and width of fourth red piece lst = [[[big_square_side - x, (big_square_side - y) * x] for x in d[big_square_side - y] if (big_square_side - x) in d] for y in [a, b]] # check every combination of possible length and width for c, d in product(lst[0], lst[1]): # has the fourth piece a known area if c[0] * d[0] not in d_red: continue # do all four pieces have a different area if len(set([c[0] * d[0], a * b, c[1], d[1]])) != 4: continue # return all four pieces return tuple(sorted([tuple(sorted([a, b])), tuple(sorted([big_square_side - a, big_square_side - c[0]])), tuple(sorted([big_square_side - b, big_square_side - d[0]])), tuple(sorted([c[0], d[0]]))])) return tuple() # areas of tiles we are given areas = sorted([504, 420, 324, 306, 270, 130, 117, 112]) # record possible tiles d_tiles = dict((x, list(divisors_pairs(x))) for x in areas) # possible areas for the big square sqs = {n * n for n in range(1, areas[-4] + 1)} area_greenred = sum(areas) # candidates for yellow area area_yellow_cands = [sq for sq in sqs if (sq + area_greenred) in sqs] # check all candidates for yellow areas for area in area_yellow_cands: big_square_side = int((area + area_greenred)**.5) yellow = int(area**.5) area_yellow = area # adjust possible red tiles to drop tiles with a big length d_red = {k: [x for x in vs if x[0] <= big_square_side and x[1] <= big_square_side] for k, vs in d_tiles.items()} d_side = dict() # dictionary per side for k, vs in d_red.items(): for x in vs: d_side[x[0]] = d_side.get(x[0], set()) | {x[1]} d_side[x[1]] = d_side.get(x[1], set()) | {x[0]} if big_square_side in d_side: # valid situation but not coded! continue # as each piece now is shorter than the side of the big square # we need to have a form so that 2 sides of different pieces are equal to # the side of the big square, forms should be similar to this one: # # +----------+--+ # | | | # +----+-----+ | # | | | | # | +-----+--+ # | | | # +----+--------+ # adjust dictionary to keep only sides <x> for which complementary side # <big_square_side> - <k> also exists d_side = {k: vs for k, vs in d_side.items() if big_square_side - k in d_side} # also adjust possible red tiles d_red = {k: [x for x in vs if big_square_side - x[0] in d_side and big_square_side - x[1] in d_side] for k, vs in d_red.items()} sol = set() for k, vs in d_red.items(): # pick a first red piece for (le, wi) in vs: # find three other red pieces which can form the outer ring chk = check(le, wi, d_side) if chk: if chk not in sol: print("answer:", *chk) sol.add(chk)LikeLike