Results 1 to 6 of 6
Like Tree2Thanks
  • 1 Post By SlipEternal
  • 1 Post By SlipEternal

Thread: Mathematical puzzle involving exponentials

  1. #1
    Newbie
    Joined
    Mar 2018
    From
    Australia
    Posts
    7

    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.

    Mathematical puzzle involving exponentials-screenshot_14.jpg

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,683
    Thanks
    1492

    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.
    Last edited by SlipEternal; Mar 20th 2018 at 03:35 AM.
    Thanks from TheFallen018
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2018
    From
    Australia
    Posts
    7

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,683
    Thanks
    1492

    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} $
    Thanks from TheFallen018
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2018
    From
    Australia
    Posts
    7

    Re: Mathematical puzzle involving exponentials

    Quote Originally Posted by SlipEternal View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,683
    Thanks
    1492

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A puzzle problem involving coinage
    Posted in the Math Puzzles Forum
    Replies: 1
    Last Post: Oct 22nd 2012, 02:22 PM
  2. Integrals involving complex exponentials
    Posted in the Advanced Applied Math Forum
    Replies: 7
    Last Post: Oct 1st 2011, 06:24 AM
  3. integration involving exponentials
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Apr 26th 2010, 10:39 AM
  4. Equation involving sum of exponentials
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: Feb 26th 2010, 01:32 PM
  5. Replies: 2
    Last Post: Jul 4th 2009, 02:37 AM

/mathhelpforum @mathhelpforum