# Solve this special combinatorics and algebra problem for me please

Two days ago, my math team teacher post this problem but I have no idea to solve it and I don't know the answer.

For all distinct positive integer here $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ is equal or less than 8, how many ways does it satisfy all those conditions,

$a-b=5$

$c-d=2$

$e-f=2$

$g-h=3$

How to generalize a method to solve those type of problem?

-
Hi Victor, what have you tried? – user02138 Feb 18 '12 at 18:47
@user02138 - i notice that for such problem to be working. All the equation must be add up to the 3/2 times # of the integer – Victor Feb 18 '12 at 18:53
@user02138 - For example, while all the equation add up to 12 while we have 8 number, i discover this by trying with 4 numbers problem, 2 numbers problems. – Victor Feb 18 '12 at 18:59
Is it (homework)? – Gigili Feb 18 '12 at 20:55
@Gigili: I think your answer is fine. (I've deleted my now-redundant comment instead.) – Lopsy Feb 18 '12 at 21:14

Other than bashing the problem with brute force (Mathematica doesn't take very long to try all $8!=40320$ possible permutations of the integers 1 through 8), I'd start by asking which pairs of distinct numbers from $\{1,2,3,4,5,6,7,8\}$ $a$ and $b$ satisfy $a-b=5$.

Further hint on that point:

If $a\le5$, then $b\not\in\{1,2,3,4,5,6,7,8\}$, ...

And where I'd go from there:

What about $c$ and $d$? How do the limitations on $a$ and $b$ interact with those on $c$ and $d$?

edit: Since a nearly-complete answer has been posted in another answer, here's the Mathematica code I used to solve it by brute-force:

#[[1]] & /@
Select[Table[{l,
l[[1]] - l[[2]] == 5 && l[[3]] - l[[4]] == 2 &&
l[[5]] - l[[6]] == 2 && l[[7]] - l[[8]] == 3}, {l,
Permutations[Range[8]]}], #[[2]] &]


and the solutions:

$a=7$, $b=2$, $c=3$, $d=1$, $e=6$, $f=4$, $g=8$, $h=5$
$a=7$, $b=2$, $c=5$, $d=3$, $e=8$, $f=6$, $g=4$, $h=1$
$a=7$, $b=2$, $c=6$, $d=4$, $e=3$, $f=1$, $g=8$, $h=5$
$a=7$, $b=2$, $c=8$, $d=6$, $e=5$, $f=3$, $g=4$, $h=1$

Also, here's how I'd solve it by hand:

The only possibilities for $a$ and $b$, based on the hints discussed above, are $(a,b)=(6,1)$, $(a,b)=(7,2)$, or $(a,b)=(8,3)$. Though I'd suggested looking at $c$ and $d$ next, I'd actually look at $g$ and $h$ next, since their difference ($3$) is the next largest difference after $a$ and $b$.

If $(a,b)=(6,1)$, then $(g,h)$ could be $(5,2)$, $(7,4)$, or $(8,5)$. On paper at this point, for these three cases, I'd have:     $\not1\;\not2\;3\;4\;\not5\;\not6\;7\;8$;     $\not1\;2\;3\;\not4\;5\;\not6\;\not7\;8$;     and $\not1\;2\;3\;4\;\not5\;\not6\;7\;\not8$ (respectively). The remaining pairs of numbers ($c$ and $d$, $e$ and $f$) each differ by two and it should be clear from these lists with the already-used numbers crossed out that none of them permit two such pairs.

If $(a,b)=(7,2)$, then $(g,h)$ could be $(4,1)$, $(6,3)$, or $(8,5)$. On paper at this point, for these three cases, I'd have:     $\not1\;\not2\;3\;\not4\;5\;6\;\not7\;8$;     $1\;\not2\;\not3\;4\;5\;\not6\;\not7\;8$; and     $1\;\not2\;3\;4\;\not5\;6\;\not7\;\not8$ (respectively). In the first case, $(c,d)$ and $(e,f)$ can be $(5,3)$ and $(8,6)$ (in either order); the second case does not allow two pairs of numbers with difference 2; in the third case, $(c,d)$ and $(e,f)$ can be $(3,1)$ and $(6,4)$ (in either order). This gives 4 solutions:
$a=7$, $b=2$, $c=3$, $d=1$, $e=6$, $f=4$, $g=8$, $h=5$
$a=7$, $b=2$, $c=6$, $d=4$, $e=3$, $f=1$, $g=8$, $h=5$
$a=7$, $b=2$, $c=5$, $d=3$, $e=8$, $f=6$, $g=4$, $h=1$
$a=7$, $b=2$, $c=8$, $d=6$, $e=5$, $f=3$, $g=4$, $h=1$

If $(a,b)=(8,3)$, then $(g,h)$ could be $(4,1)$, $(5,2)$, or $(7,4)$. On paper at this point, for these three cases, I'd have:     $\not1\;2\;\not3\;\not4\;5\;6\;7\;\not8$;     $1\;\not2\;\not3\;4\;\not5\;6\;7\;\not8$;     and $1\;2\;\not3\;\not4\;5\;6\;\not7\;\not8$ (respectively). It should be clear from these lists with the already-used numbers crossed out that none of them permit two pairs with difference 2.

-
Do you have a generalize way to solve these type of question, otherwise i have to solve million of those... – Victor Feb 19 '12 at 2:14
$+100$ for the "Also, here's how I'd solve it by hand" part. – Gigili Feb 19 '12 at 19:19

You have eight distinct positive integers from 1 to 8. Now considering the first equation:

$a-b=5$ : There are three possibilities for this to happen,

$(a,b)$ : $(6,1)$, $(7,2)$ or $(8,3)$

• Suppose $a=6$ and $b=1$, so considering other equations we should have $(4,2)$ and $(5,3)$, then there's no valid answer for the last equation $g-h=3$.
• Suppose $a=8$ and $b=3$, for the second and third we can have $(4,2)$ and $(7,5)$, again the last one has no valid answer.

$a=7$, $b=2$, $c=3$, $d=1$, $e=6$, $f=4$, $g=8$ and $h=5$

or

$a=7$, $b=2$, $c=6$, $d=4$, $e=3$, $f=1$, $g=8$ and $h=5$

or

$a=7$, $b=2$, $c=8$, $d=6$, $e=5$, $f=3$, $g=4$ and $h=1$.

I solved the whole problem once again and found another answer. To make sure that I didn't make a mistake this time, I checked it using Mathemtica:

{{$a -> 7, b -> 2, c -> 3, d -> 1, e -> 6, f -> 4, g -> 8, h -> 5$},
{$a -> 7, b -> 2, c -> 5, d -> 3, e -> 8, f -> 6, g -> 4, h -> 1$},
{$a -> 7, b -> 2, c -> 6, d -> 4, e -> 3, f -> 1, g -> 8, h -> 5$},
{$a -> 7, b -> 2, c -> 8, d -> 6, e -> 5, f -> 3, g -> 4, h -> 1$}}

That proves that I missed another possibility. To make it short, I wouldn't solve such problems by hand (as I did), the probability of missing something important is quite high.

-
I have more than 2 solutions. – Isaac Feb 18 '12 at 21:13
@Isaac: I suspected something like that, how so? Did you follow my solution to the end? – Gigili Feb 18 '12 at 21:18
I agree up to "So the answer could be:" and I agree that if you've got one solution, you can swap $c$ and $d$ with $e$ and $f$, but you didn't describe how you got any of the values of $c$, $d$, $e$, $f$, $g$, or $h$. – Isaac Feb 18 '12 at 21:20
@Isaac: You agree that there are three possibilities for the first one? I took one of them each time and considered the rest to a contradiction. Note that the eight integer numbers should be distinct. – Gigili Feb 18 '12 at 21:36
Given $a=7$ and $b=2$, there are values for $c$ other than 3 and 6 that work. – Isaac Feb 18 '12 at 23:26

Draw the following figure: $$\circ\quad\circ\quad\bullet\quad\circ\quad\circ\ \ |\ \circ\quad\circ\quad\bullet\quad\circ\quad\circ\qquad.$$ Here the bullets $\bullet$ represent $a$ and $b$. Draw near the upper rim of a second piece of paper the following figure: $$\bigcirc\quad\circ\quad\circ\quad\bigcirc\qquad,$$ where now the big circles $\bigcirc$ represent $g$ and $h$. By moving the second figure horizontally under and along the first you can immediately see that only the choice $$\circ\quad\bigcirc\quad\bullet\quad\circ\quad\bigcirc\ \ |\ \circ\quad\circ\quad\bullet\quad\circ\quad\circ$$ and its reflection with respect to $|$ allow an admissible selection of the remaining four numbers $c$, $d$, $e$, $f$ – the word "allow" meaning that in the end we have $8$ consecutive numbers selected.

-