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×n, 2×n−1, ...n×1.).

Conjecture: No two disjoint subsets of any S-tileset can be tiled to form two areas of identical size and shape.

Can you either prove the conjecture or find a counter-example.

$\endgroup$
  • $\begingroup$ Another conjecture: A subset (of an S-tileset) having more than one tile in it cannot tile a rectangle $\endgroup$ – James Waldby - jwpat7 Aug 17 '14 at 23:18
  • 2
    $\begingroup$ I know this is a math puzzle, but the way it's written feels like it should go on Math.SE under the "puzzle" tag rather than actually here. $\endgroup$ – Joe Z. Aug 17 '14 at 23:49
  • $\begingroup$ Do you allow rotation? If so, the answer is trivial - simply use the 1xn tile normally, and the nx1 tile rotated 90 degrees. They are disjoint, yet form two areas of identical size and shape. $\endgroup$ – Trenin Oct 3 '14 at 18:41
  • $\begingroup$ @Trenin No, the tiles are oriented, so rotation is specifically disallowed. $\endgroup$ – Penguino Oct 5 '14 at 20:30
  • 1
    $\begingroup$ @jwpat7 - a counterexample to your conjecture: imgur.com/k11J8zm. This is actually parametric in the n=14 set, there's a number of rectangles with the same layout. I suspect this might help find a counterexample to the posted conjecture. $\endgroup$ – YenTheFirst Oct 8 '14 at 1:19
4
$\begingroup$

Here's a counter-example to the conjecture, for N=860

(you may need to open the image in a new tab to read the sizes in the image) A counter-example

The set of rectangles used:

Shape 1

  • 602x259
  • 210x651
  • 28x833
  • 133x728
  • 469x392
  • 679x182
  • 707x154
  • 840x21

Shape 2

  • 196x665
  • 70x791
  • 161x700
  • 413x448
  • 609x252
  • 770x91
$\endgroup$
  • $\begingroup$ That is an excellent result. Did you solve it using Diophantine equations? $\endgroup$ – Penguino Oct 20 '14 at 22:41
  • $\begingroup$ Sort of. I set up systems of linear equations, and used sympy to solve or simplify them as much as possible. This ruled out a lot of candidates on its own (two sides would have the same algebraic length, for example). The system describing these two shapes ends up having only 1 free variable, so it's just a matter of picking the first one that gives integers for all sides. $\endgroup$ – YenTheFirst Oct 21 '14 at 0:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.