Mod Problem

  • Thread starter ramsey2879
  • Start date
  • #1
841
0

Main Question or Discussion Point

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?
 

Answers and Replies

  • #2
841
0
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?
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".
 
  • #3
144
0
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.
 
  • #4
841
0
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.
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:

Related Threads on Mod Problem

Replies
5
Views
4K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
17
Views
4K
Replies
12
Views
583
Replies
8
Views
4K
Replies
2
Views
1K
Replies
7
Views
10K
Top