10

My young daughter and I love doing jigsaw puzzles together. The other day, we had a quite difficult one: 7 by 7 pieces!

We started as usual by splitting the pieces into 2 stacks: the edge pieces on one side, the middle pieces on the other side.

Before putting the edges together, we noticed that there were almost the same number of pieces in each stack:

Our 7x7 puzzle

I wondered then... our puzzle collection is huge! We have all the possible sizes, from 1x2 to 100x100 pieces.

Can we find one (or even more?) in our collection containing exactly the same number of edges pieces and middle pieces?

Thomas
  • 468
  • 2
  • 7
  • Just to be 100% clear, could you include your definitions of middle and edge pieces? For example, if you have a 2x3 puzzle, would you define all of the pieces to be edge pieces? – NeedAName Aug 19 '15 at 15:29
  • Yes, for a 2xN puzzle, all pieces would be edge pieces. – Thomas Aug 19 '15 at 20:24

3 Answers3

14

What you're looking for are numbers $X$ and $Y$ where $2X + 2(Y-2) = (X-2)*(Y-2)$. This is generalized; a few possible (and practical) solutions would be:

  • $5$ by $12$, with $30$ of both edge and middle pieces.
  • $6$ by $8$, with $24$ of both edge and middle pieces.
Bailey M
  • 16,973
  • 2
  • 69
  • 119
  • I wonder, is there a case with two odd numbers? Because then you'd have a single piece in the center like the example. – Kingrames Aug 19 '15 at 15:34
  • 1
    There's no possibility with two odd numbers, since the left side of the equation would come out to an even number (always), while the right side would come out to an odd number (always). The closest you can get is within one, which the example fulfills (24 side pieces, 25 middle pieces). – Bailey M Aug 19 '15 at 15:35
  • Nice, I think that helps explain the relationship better. – Kingrames Aug 19 '15 at 15:37
  • 1
    You're right, the next possible solution would be $10008$ by $858654$. But I don't think the OP wants more solutions than your two. –  Aug 19 '15 at 15:44
  • That would be a hell of a puzzle. – Bailey M Aug 19 '15 at 15:45
  • 4
    Assuming you could scan about 10 pieces a second, it could take up to 27 years just to find the four corner pieces! – Gordon K Aug 19 '15 at 15:48
  • 1
    @LuxxMiner Wouldn't $10008 \times 858654 $ have much more middle pieces? – Rohcana Aug 19 '15 at 17:20
  • @Anachor You're right, I really don't know why my program messed up there... –  Aug 19 '15 at 17:48
  • 4
    @LuxxMiner Actually you don't need a program, The equation is equivalent to $(x-4)(y-4)=8$ Then we can factorize 8, and find only two incongruent solutions. – Rohcana Aug 19 '15 at 17:57
  • 2
    @LuxxMiner I figured out your problem, you are having a good ol' integer overflow issue. $10008 \times 858654 \equiv 3474640 \pmod {2^{31}}$ and $2 \times (10008 + 858654 - 2) = 1737320$ which is half the previous figure. I guess you didn't use python then. :) – Rohcana Aug 19 '15 at 23:25
  • @WorldSEnder No, as you see $y-4$ must divide $8$ and hence $y-4 \in$ $ {-8,-4,-2,-1 ,1,2, $ $ 4,8 }$ The negative values don't yield a solution. The positive ones only generate the above two twice each. – Rohcana Aug 20 '15 at 00:33
  • All current solutions are correct but you were the first to answer, so I will accept yours! Also, good point from @Anachor with the factorization, which proves those solutions are the only ones. – Thomas Aug 20 '15 at 06:12
4

For an n x m puzzle, the number of edge pieces, E, is defined by

$2n+2(m-2)$

and the number of middle pieces, M, is then defined by

$nm-E$

If we want to find a puzzle size for which E=M, then we are looking for the case where

$nm-E=E \implies nm=2E \implies nm=4n+4m-8$

I wrote a quick nested for loop to search for solutions and found the pairs

$n=5, m=12$ and $n=6,m=8$
(In either case, swapping $n$ and $m$ is irrelevant i.e. $m=12,n=5$ leads to the same result)

CodeNewbie
  • 11,753
  • 2
  • 45
  • 87
NeedAName
  • 11,610
  • 1
  • 24
  • 62
2

Our goal is to find such $n$ and $m$ that $nm = 2(n-2)(m-2)$. They can't be equal of course.

Assuming $n<m$, then $\dfrac n{n-2} > \sqrt2$, so $n<8$.

Then again, $2(n-2) > n$, therefore $4<n<8$.

The equality $\frac{2n-4}n = \frac m{m-2}$ can be modified as $\frac{n-4}n = \frac2{m-2}$, so $\frac{2n}{n-4}$ must be an integer equal to $m-2$, making 8 divisible by $n-4$. The latter can be 1 or 2, so either $n=5, m=12$ or $n=6, m=8$.

Disclaimer: I know I could just try seeing if it can be done for all 3 possible values of $n$ after narrowing it down, but didn't feel like it.

grg
  • 207
  • 3
  • 6
Nautilus
  • 6,534
  • 10
  • 32
  • 3
    Alternatively, rearrange $nm=2(n-2)(m-2)$ to $(n-4)(m-4)=8$ and compare with the factorizations $(\pm 1)\cdot(\pm 8)$ and $(\pm2)\cdot(\pm 4)$ of $8$, leading to the positive solutions $(5,12)$ and $(6,8)$ – Hagen von Eitzen Aug 19 '15 at 20:28