3
$\begingroup$

We have a 2x2 grid and 10 different colours. I want to paint such that adjacent grids are painted with different colors. How many ways can i do this?

I labeled the grids as:
A B
C D

Scenario 1: B and C different colors.
1)A has 10 colors to choose from.
2)B has 9 colors to choose from
3)C has 8 colors to choose from
4)D has 8 colors to choose from
Total ways: 10*9*8*8 = 5760 ways

Scenario 2: B and C have same colors.
1)A has 10 colors to choose from.
2)B has 9 colors to choose from
3)C has 9 colors to choose from
4)D has 9 colors to choose from
Total ways: 10*9*9*9 = 7290 ways

Total ways = 7290 + 5760 = 13050 ways.

Did i do it correctly?
$\endgroup$
  • 1
    $\begingroup$ In the scenario 2 when you chose a color for B you don't chose for C after because they have the same color, but there is no other mistake. $\endgroup$ – Jennifer Apr 23 '16 at 7:05
  • $\begingroup$ OH yes wow thanks! $\endgroup$ – RStyle Apr 23 '16 at 7:06
2
$\begingroup$

As Jennifer pointed out in a comment, you have one excess factor $9$ in scenario $2$. Correcting that yields $10\cdot9\cdot8\cdot8+\cdot10\cdot9\cdot9=90(64+9)=6570$.

Another way to do this is via inclusion-exclusion. We have four conditions, one for each pair of adjacent cells. There are $10^{4-k}$ options that fulfil $k$ conditions, except for $k=4$ there are $10$ options instead of $1$, for a total of

$$ 9+\sum_{k=0}^4(-1)^k10^{4-k}\binom4k=9+10^4\left(1-\frac1{10}\right)^4=9+9^4=6570. $$

Another solution: Start at A with $10$ options and go clockwise, with $9$ options per step, which makes $10\cdot9^3$. Then subtract the configurations in which A and C have the same colour, of which there are $10\cdot9\cdot8$, for a total of $10\cdot9(81-8)=6570$.

If you just want a rough estimate, start at A and go clockwise; by the time you get back to A the information which colour you started with will almost be lost, so the probability that you end up with the same colour is almost exactly $1$ in $10$, which effectively reduces the options for the first colour from $10$ to $9$, yielding an estimate of $9^4=6561$.

See also In how many ways can we colour $n$ baskets with $r$ colours?

$\endgroup$
  • $\begingroup$ I like using awk to verify my results for simple combinatorics. Here, awk -v n=10 'BEGIN { for (a=0;a<n;a++) for (b=0;b<n;b++) for (c=0;c<n;c++) for (d=0;d<n;d++) i += (a!=b && a!=c && b!=d && c!=d); printf "%d\n", i }' will print 6570 as one would expect. For n=100, it takes almost half a minute to reach the result (96059700), so for brute-forcing large problems it's not that good. It's a simple language, but has associative arrays, which helps with many types of combinatorics problems. $\endgroup$ – Nominal Animal Apr 23 '16 at 9:57

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.