From The Sunday Times, 10th August 1975 [link]
A farmer grows apples in an orchard divided into plots —three to the East and three to the West of a central path. The apples are of two types — for eating (Cox, Laxton, Pearmain) and for cider making (Tremlitt, Coppin, Kingston).
Adjacent plots contain apples of different basic type. The apples are of six colours (red, green, russet, golden, orange, yellow) and of six tastes (sweet, sour, acid, tart, pleasant, bitter).
They ripen at different times, either early or late in July, August and September. Those ripening in early or late September are in plots directly opposite. Those South of Pearmain do not ripen in August. Tart are directly West of the acid variety, which ripens in early August. Yellow apples and those maturing in late September are adjacent. Yellow and orange are of the same type. Orange are North of pleasant and also North of Pearmain. Kingstons are adjacent to golden. Green is South of bitter.
Cox ripen in early July, and Laxtons ripen early in a different month. Tremlitts are red, and Kingstons mature after Coppins, which are not sour.
If cider apples taste unpleasant, what are the characteristics of the apples in North East plot? (Name, colour, taste, ripens).
This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 2 (1981).
I think the puzzle as published in The Sunday Times and in the book is open to interpretation, and my first attempt using a reasonable interpretation gave two solutions (neither of which are the published solution). After examining the given solution in the book I think the following wording is clearer:
A farmer grows apples in an orchard divided into plots — three to the East and three to the West of a central track. Adjacent plots are separated by a shared fence. The apples are of two basic types — for eating (Cox, Laxton, Pearmain) and for cider making (Tremlitt, Coppin, Kingston).
Neighbouring plots contain apples of different basic type. The apples are of six colours (red, green, russet, golden, orange, yellow) and of six tastes (sweet, sour, acid, tart, pleasant, bitter).
They ripen at different times, either early or late in July, August and September. Those ripening in early or late September are in plots directly opposite each other. Those directly South of Pearmain do not ripen in August. Tart are directly West of the acid variety, which ripens in early August. Yellow apples and those maturing in late September are in adjacent plots. Yellow and orange are of the same basic type. Orange are directly North of Permain, which are pleasant. Kingstons and golden are in adjacent plots. Green is directly South of bitter.
Cox ripen in early July, and Laxtons ripen early in a different month. Tremlitts are red, and Kingstons mature after Coppins, which are not sour.
If cider apples are neither pleasant nor sweet, what are the characteristics of the apples in North-East plot?
[teaser734]
Pete Good, and 
Frits are discussing. 
GeoffR, and 
S2T2 
Jim Randell 2:54 am on 20 October 2024 Permalink |
See also: BrainTwister #15.
The two sizes of tiles are 10 cm × 20 cm and 20 cm × 20 cm, so we can work in units of decimetres and just consider 1×2 and 2×2 tiles.
This Python program packs increasing numbers of tiles into a tray 2 units high, proceeding from left to right, and also constructs a representation of each packing.
It runs in 96ms. (Internal runtime is 29ms).
from enigma import (irange, inf, decompose, icount, is_square, printf) # find packings for <a> 2x1 and <b> 2x2 tiles def solve(a, b, ss=''): # are we done? if 0 == a == b: yield ss else: if a > 1: # place 2x 2x1 tiles horizontally yield from solve(a - 2, b, ss + '=') if a > 0: # place 1x 2x1 tile vertically yield from solve(a - 1, b, ss + '|') if b > 0: # place 1x 2x2 tile yield from solve(a, b - 1, ss + 'O') # consider total number of tiles for t in irange(3, inf): r = 0 # count results with up to 3 digits # split into 2x1 (more) and 2x2 tiles for (b, a) in decompose(t, 2, increasing=1, sep=1, min_v=1): # count the number of ways to place the tiles n = icount(solve(a, b)) # look for cases where n is a 3-digit square if n < 1000: r += 1 if n > 99 and is_square(n): printf("t={t}: a={a} b={b} -> {n} ways; length = {x}", x=a + 2 * b) # are we done? if r == 0: breakIf we don’t generate the representations of the packings we can write a faster program.
The following program has an internal runtime of 227µs.
from enigma import (irange, inf, decompose, cache, printf) # number of packings for <a> 2x1 and <b> 2x2 tiles @cache def P(a, b): # are we done? if 0 == a == b: return 1 r = 0 # place 2x 2x1 tiles horizontally if a > 1: r += P(a - 2, b) # place 1x 2x1 tile vertically if a > 0: r += P(a - 1, b) # place 1x 2x2 tile if b > 0: r += P(a, b - 1) return r # target values = 3-digit squares tgt = set(i * i for i in irange(10, 31)) # consider total number of tiles for t in irange(3, inf): r = 0 # count results with up to 3 digits # split into 2x1 (more) and 2x2 tiles for (a, b) in decompose(t, 2, increasing=-1, sep=1, min_v=1): # count the number of ways to place the tiles n = P(a, b) # look for cases where n is a 3-digit square if n < 1000: r += 1 if n > 99 and n in tgt: printf("t={t}: a={a} b={b} -> {n} ways; length = {x}", x=a + 2 * b) # are we done? if r == 0: breakSolution: The box is 110 cm long. There are 3 square tiles.
There are 8 tiles in total, 3 square and 5 rectangular. And they can fit into the box in 256 (= 16^2) different ways.
See also: OEIS A038137.
LikeLike
Frits 11:55 am on 20 October 2024 Permalink |
My original program performed weaving of the list of squares with the list of rectangles but as we are only interested in the number of combinations I have used the combinatorial C formula.
from math import factorial as fact # number of possible combinations C = lambda n, r: fact(n) / (fact(r) * fact(n - r)) # loop over number of tiles for t, _ in enumerate(iter(bool, 1), 3): # infinite loop below1000 = 0 # choose number of square tiles for s in range(1, (t + 1) // 2): r = t - s # number of rectangular tiles # fill box with <s> squares and <r> rectangles # suitable selection of rectangular pieces rps = [["|"] * v + ["="] * (h // 2) for v in range(r + 1) if (h := (r - v)) % 2 == 0] c = 0 for rp in rps: nv = rp.count("|") # C(len(rp), nv) = len(set(permutations(rp))) c += C(len(rp) + s, s) * C(len(rp), nv) if c < 1000: below1000 = 1 # three-digit perfect square if c > 99 and (round(c**.5))**2 == c: print(f"answer: {10 * (2 * s + r)} cm long and with {s} square tiles") if below1000 == 0: break # no need to check with more tilesLikeLike
Pete Good 5:17 pm on 20 October 2024 Permalink |
Jim, Frits’s program produces the right answer but your answer needs to be multiplied by 10.
LikeLike
Jim Randell 6:01 pm on 20 October 2024 Permalink |
@Pete: My programs use units of 1 decimetre.
LikeLike