Teaser 2890: Squares on cubes
From The Sunday Times, 11th February 2018 [link] [link]
Liam has a set of ten wooden cubes; each has a different number (from 1 to 10) painted on one face (the other five faces are blank). He has arranged them in a rectangular block with all numbers upright and facing outwards. Each vertical side of the block shows some numbers which can be read as a number that is a perfect square. No two square numbers have the same number of digits.
Which square number must be present?
[teaser2890]
GeoffR are discussing. 
John Crabtree and 
Frits, 
S2T2 
Jim Randell 2:51 pm on 28 November 2019 Permalink |
The cubes are placed on the table, so that the numbers are showing on vertical faces. They are then slid around on the table to arrange them into a contiguous rectangular block with all the numbers showing on the outside vertical edges of the block.
The cubes must be arranged into a 2×5 block (a 1×10 block is not possible), and each of the 4 vertical sides of the block reads as a square number. And each of the 4 square numbers has a different number of digits.
The sides composed of 2 blocks cannot involve 10 (as none of 10, 10_, _10 are square numbers), so they must display square numbers made of 1 number (1 digit) and 2
numbers (2 digits) and the 5 block sides must show squares made of 3 numbers (3 digits) and 4 numbers (5 digits, including 10).
This Python program runs in 103ms.
Run: [ @repl.it ]
from enigma import (irange, subsets, concat, is_square, Accumulator, diff, join, printf) # single digits (10 must appear in the 4-number square) digits = irange(1, 9) # make squares from k numbers def squares(numbers, k): for ns in subsets(numbers, size=k, select="P"): s = int(concat(ns)) if is_square(s): yield ns # find values common to all solutions r = Accumulator(fn=set.intersection) # choose a 1 number square [1, 4, 9] for s1 in squares(digits, 1): # choose a 2 number square [not 10] for s2 in squares(diff(digits, s1), 2): # choose a 3 number square [not 10] for s3 in squares(diff(digits, s1 + s2), 3): # choose a 4 number square [must have 10] for s4 in squares(diff(digits, s1 + s2 + s3) + (10,), 4): # turn the squares into strings ss = tuple(map(concat, (s1, s2, s3, s4))) printf("{s1} {s2} {s3} {s4}") r.accumulate(set(ss)) printf("common squares = {r}", r=join(sorted(r.value), sep=", "))Solution: The square number 9 must be present.
The three possible arrangements for the square numbers are:
Here is a diagram of the first arrangement.
Imagine the cubes are laid out like a 2×5 block of chocolate viewed from above. The numbers are etched on the the sides of the cubes. But the block has started to melt and so the bottom of it has splayed out, allowing us to see all four of the square numbers when viewed from directly above:
LikeLike
GeoffR 8:23 am on 30 November 2019 Permalink |
% A Solution in MiniZinc include "globals.mzn"; % Looking for 1-digit, 2-digit, 3-digit and 5-digit squares % on cubes to use up all 10 numbers (1-10) in a 5 by 2 block % of cubes in same arrangement as Jim var 0..9: A; var 0..9: B; var 0..9: C; var 0..9: D; var 0..9: E; var 0..9: F; var 0..9: G; var 0..9: H; var 0..9: I; var 0..9: J; var 0..9: K; % 2,3 and 5 digit squares var 10..99: BC = 10*B + C; var 100..999: DEF = 100*D + 10*E + F; var 10000..99999: GHIJK; set of int: sq2 = {n*n | n in 4..9 }; set of int: sq3 = {n*n | n in 10..31}; set of int: sq5 = {n*n | n in 100..316}; % Four squares constraint A == 4 \/ A == 9; constraint BC in sq2; constraint DEF in sq3; constraint GHIJK in sq5; constraint G == GHIJK div 10000 /\ H == GHIJK div 1000 mod 10 /\ I = GHIJK div 100 mod 10 /\ J == GHIJK div 10 mod 10 /\ K = GHIJK mod 10; % Number 10 must be in the five digit square GHIJK constraint (G == 1 /\ H = 0) \/ (H == 1 /\ I = 0) \/ (I == 1 /\ J = 0) \/ (J == 1 /\ K = 0); % check digit '1' occurs twice only i.e as 1 and 10 constraint count_eq([A, BC div 10, BC mod 10, DEF div 100, DEF div 10 mod 10, DEF mod 10, G, H, I, J, K ], 1, 2); % the set of digits used var set of int: my_set = {A, BC div 10, BC mod 10, DEF div 100, DEF div 10 mod 10, DEF mod 10, G, H, I, J, K }; % maximum set of digits used set of int: all_dig == {1,2,3,4,5,6,7,8,9,0}; constraint my_set == all_dig; solve satisfy; % Four squares output [ "Squares: 1-digit = " ++ show(A) ++ ", 2-digit = " ++ show(BC) ++ ", 3-digit = " ++ show(DEF) ++ ", 5-digit = " ++ show(GHIJK)]; % Squares: 1-digit = 9, 2-digit = 36, 3-digit = 784, 5-digit = 11025 % ---------- % Squares: 1-digit = 9, 2-digit = 81, 3-digit = 576, 5-digit = 23104 % ---------- % Squares: 1-digit = 9, 2-digit = 81, 3-digit = 324, 5-digit = 51076 % ---------- % ========== % Finished in 684msecWithout the constraint that the digit one is the duplicated digit, I found three more possible sets of squares:
(4,36,289, 51076)
(9,36,784,21025)
(9,25,784, 36100)
@Jim: Please confirm your run-time for this code.Thanks,
LikeLike
Jim Randell 8:43 am on 1 December 2019 Permalink |
@Geoff: On my machine I get a comparative runtime of 377ms for the code you posted (using the gecode solver – the chuffed solver fails on this model).
LikeLike