# Thread: Mathematical puzzle involving exponentials

1. ## Mathematical puzzle involving exponentials

Hi, I'm trying to solve this puzzle I've come against, and I'm not quite sure what the best way to go about it is. Here's the question.

So, it seems to me that the first thing you'd do is take the maximum number of combinations, which I'm guessing should be 2^4036, due to there being 4036 boxes that each have a possible 2 combinations. Let's take the example with A and B, since the top row is 1 in both boxes, A cannot equal B. Therefore, if A = 0, B has to be equal to 1, or vice versa. By that logic, that takes two possible combinations out of a 4x4 block, making the block instead of having 2^4 possibilities, it now has 2^3 possible combinations. By that logic, there should be 2^(3027) possible numbers.

I feel though that I've missed a good number of constraints. What do you guys think?

Thanks.

2. ## Re: Mathematical puzzle involving exponentials

Look at a single 4x4 block. Find the forbidden set ups:

0,0
0,0

0,0
1,1

1,1
0,0

1,1
1,1

So, every 4x4 block has 4 forbidden positions.

Now, we use a technique called inclusion/exclusion. We break up the 2018x2 blocks into 2017 2x2 blocks. Number them 1 to 2017 (blocks 1 and 2 overlap, 2 and 3 overlap, etc). The event that block n is in a forbidden position is $A_n$.

So, you are looking for:
$\displaystyle 2^{4036}+\sum_{n=1}^{2017}(-1)^n \sum_{ \begin{matrix} I \subseteq [2017] \\ |I|=n \end{matrix} } \left| \bigcap_{k\in I} A_k \right|$

Where $[2017]=\{1,2,\ldots,2017\}$

To figure out how to calculate this, we will start with smaller problems and work our way up. If we just have a 2x2 block, the total number of ways to put numbers in it is:
$2^4-2^2=16-4=12$
For a 2x3 block, it is:
$2^6-2^2\cdot 4-2^2\cdot 4+4=64-16-16+4=36$
For a 2x4 block, it is:
$2^8-3\cdot 2^4\cdot 4 + 2\cdot 2^2\cdot 4 + 4\cdot 4-4=2^8-3\cdot 2^6+3\cdot 2^4-2^2$

And now a pattern emerges.
$\displaystyle \sum_{n=0}^{2017} (-1)^n\dbinom{2017}{n}2^{4036-2n}$

sum[(-1)^n*Binom[2017,n]*2^(4036-2n),{n,0,2017}] - Wolfram|Alpha Results

I leave it to you to prove this is the correct answer.

3. ## Re: Mathematical puzzle involving exponentials

Hmm, that seems to work, but is there a way to simplify it? I was thinking that the answers seem to work out to the last answer multiplied by 3. Is there a way to do that, and sum the numbers? Cheers

4. ## Re: Mathematical puzzle involving exponentials

Use the Binomial Theorem:

$\displaystyle \sum_{n=0}^{2017}(-1)^n \dbinom{2017}{n} 2^{4036-2n}=4\sum_{n=0}^{2017}\dbinom{2017}{n}(-1)^n4^{2017-k}=4(4-1)^{2017} =4\cdot 3^{2017}$

5. ## Re: Mathematical puzzle involving exponentials

Originally Posted by SlipEternal
Use the Binomial Theorem:

$\displaystyle \sum_{n=0}^{2017}(-1)^n \dbinom{2017}{n} 2^{4036-2n}=4\sum_{n=0}^{2017}\dbinom{2017}{n}(-1)^n4^{2017-k}=4(4-1)^{2017} =4\cdot 3^{2017}$
Thanks for that. I ended working it out before seeing your reply, but your method clears some things up, and allows me to clarify some things a little more clearly. Thanks again.

6. ## Re: Mathematical puzzle involving exponentials

Another way to look at the problem:
Choose for the first column: 4 possibilities
$\begin{matrix}a \\ b\end{matrix}$
Where $a,b \in \{ 0,1 \}$
Choose for the second column: 3 possibilities
$\begin{matrix}c \\ d \end{matrix} \neq \begin{matrix} a\\ b \end{matrix}$
Where $c,d \in \{ 0,1 \}$

Similarly for every column after. You have 3 possibilities for every column after the first because it cannot equal the previous column.

By the product principle, there are $4\cdot 3^{2017}$ possibilities. Much more direct approach.