Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mod Problem

  1. Oct 1, 2012 #1
    I was doing a brain treaser where the letters A-H had to be put into an array 2 by 4 such that no letter is adjacent or diagonal to a letter one unit different. That is a C can't be above, below, to one side of, or diagonal from a B or D. I solved the problem but the thought occured to me that using modular logic it can easily be proven that the H has to be above,below,to one side of, or diagonal to the A. In other words, it is immposible to put the numbers 1-8 into an 2 by 4 square box array, such that where each every set of boxes that touch either by a side
    or corner the difference between the 2 boxes mod 8 is more than 1. Does any one care to give a simple proof?
     
  2. jcsd
  3. Oct 2, 2012 #2
    Proof:let the two rows of boxes be numbered 1-2 and the 4 boxes on each row be numbered 1-4. If the boxes are filled with numbers 0-7, each number except the 0 and seven have two neighboring numbers which differed by 1, but the numbers in boxes (1,2) and (2,2) both touch all boxes but (1,4) and (2,4). Mod 8 each number has two neighbors, if the numbers in boxes (1,2) and (2,2) share a neighbor, there are still three numbers but only two boxes to fill. Thus it is impossible to fill the 8 boxes with numbers 0-7 so that no two touching boxes have a neighboring numbers in the boxes. But mod 9, 0 is not a neighbor to 7, thus 0 and 2 can be placed in boxes (1,2) and (2,2) and the two neighbors, 1 and 3 can be placed in boxes (1,4) and (2,4). Likewise, 7 and 5, can be placed in boxes (2,3) and (1,3) and the two neighbors, 4 and 6 can be placed in boxes (1,1) and (2,1). 0 corresponds to "A" and 7 corresponds to "H".
     
  4. Oct 3, 2012 #3
    Assume it is possible. Then every 2x2 square must be filled with numbers, no two of which are consecutive mod 8. Since the square contains 4 numbers, and the 4 gaps between the numbers are all at least 2, and sum to 8, we conclude that all the numbers in the square have the same parity, which then also holds for the entire array, and we have a contradiction.
     
  5. Oct 4, 2012 #4
    In other words, a 2X2 square must have only the numbers 0,2,4,6 or 1,3,5,7 since there is always a 3 gap difference between the smallest and largest number. However, when you note that there are 3 such 2 by 2 squares in a 2 by 4 array and only 2 possible sets of 4, then you have a contridiction. Thanks
     
    Last edited: Oct 4, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook