20071113, 15:22  #1 
Dec 2005
3×5×13 Posts 
Composite checkerboard
The numbers 1,2,...,100 are written in cells of a table 10 x 10, each number is written once. By one move, we may interchange numbers in any two cells.
After how many moves may we get a table, in which the sum of numbers in every two adjacent (by side) cells is composite. I can prove an easy upperbound, but I think it can be sharpened 
20071113, 15:33  #2 
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
43×103 Posts 
1. Are we starting with the numbers in order Left to right, top to bottom?
2. Can we only exchange adjacent numbers (sidebyside or one above the other)? 3. Does the same adjacent rule as in 2 apply for the final result? 
20071113, 15:48  #3  
"Lucan"
Dec 2006
England
6,451 Posts 
Quote:
1. No 2. No 3. Yes 

20071113, 16:01  #4 
Dec 2005
11000011_{2} Posts 
1) numbers are randomly placed
2) exchange between any two numbers is possible, not just adjacently placed numbers 3) final result applies to adjacent numbers 
20071114, 02:02  #5 
May 2004
New York City
2×2,099 Posts 
I can produce the desired configuration in (at most) 45 exchanges.
Is that even close to your upper bound? Here's how: Step 1: Separate the grid into two halves consisting of five rows of even numbers next to five rows of odd numbers. This takes at most 25 exchanges, and leaves all adjacent squares either both even or both odd (except along the boundary between evens and odds) so that their sum is even hence composite. Step 2: In at most 10 exchanges, place even multiples of 3 on that boundary row of evens, and in at most 10 exchanges place odd multiples of 3 on that adjacent boundary row of odds. This leaves the two halves even and odd, and makes the sums across the boundary multiples of 3 hence composite. Thus in at most 25+10+10 = 45 exchanges, all adjacent cells sum to a composite number. 
20071114, 03:52  #6 
Jun 2003
4,723 Posts 
The 10 swaps of the even "boundary" values can be avoided if we swap just the odds using the formula 99<even counterpart>

20071114, 07:23  #7 
Dec 2005
3·5·13 Posts 
I get to 35 too as upperbound but I would be surprised if there were a configuration where 35 moves are actually needed

20071114, 16:01  #8  
"Lucan"
Dec 2006
England
1933_{16} Posts 
Quote:
at least five(?) of the boundary pieces will be involved. By doing these first, surely we can get the cross boundary sum associated with these pieces to be composite, reducing the 10 boundary swaps subsequently needed. David 

20071114, 16:34  #9 
"Lucan"
Dec 2006
England
6,451 Posts 

20071114, 17:56  #10 
Jun 2003
The Texas Hill Country
2·541 Posts 

20071114, 18:09  #11 
Jun 2003
The Texas Hill Country
2×541 Posts 
Leave it to the last.
There are 10 odd tokens whose value is a multiple of 5. At most 9 of them could be otherwise required on the boundary. Therefore there is at least one available to be paired with "100" Last fiddled with by Wacky on 20071114 at 20:21 Reason: Clarify that I was referring to only the tokens on the "odd" side 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
is M21934219 composite ?  S485122  Data  50  20110110 10:28 
S_N cycles in LL done on composite M(p)  tichy  Math  1  20101223 16:47 
The composite conjecture  Carl Fischbach  Miscellaneous Math  8  20100702 08:03 
F10,21=10^(2^21)+1 is composite  Shaopu Lin  Factoring  2  20041031 13:48 
Checkerboard Problem  Kevin  Puzzles  4  20030727 01:11 