mersenneforum.org Composite checkerboard
 Register FAQ Search Today's Posts Mark Forums Read

 2007-11-13, 15:22 #1 Kees     Dec 2005 22×72 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
 2007-11-13, 15:33 #2 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 32×7×71 Posts 1. Are we starting with the numbers in order Left to right, top to bottom? 2. Can we only exchange adjacent numbers (side-by-side or one above the other)? 3. Does the same adjacent rule as in 2 apply for the final result?
2007-11-13, 15:48   #3
davieddy

"Lucan"
Dec 2006
England

2·3·13·83 Posts

Quote:
 Originally Posted by petrw1 1. Are we starting with the numbers in order Left to right, top to bottom? 2. Can we only exchange adjacent numbers (side-by-side or one above the other)? 3. Does the same adjacent rule as in 2 apply for the final result?
I think the answers are clearly:
1. No
2. No
3. Yes

 2007-11-13, 16:01 #4 Kees     Dec 2005 22×72 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
 2007-11-14, 02:02 #5 davar55     May 2004 New York City 2·32·5·47 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.
 2007-11-14, 03:52 #6 axn     Jun 2003 479010 Posts The 10 swaps of the even "boundary" values can be avoided if we swap just the odds using the formula 99-
 2007-11-14, 07:23 #7 Kees     Dec 2005 22·72 Posts I get to 35 too as upperbound but I would be surprised if there were a configuration where 35 moves are actually needed
2007-11-14, 16:01   #8
davieddy

"Lucan"
Dec 2006
England

2×3×13×83 Posts

Quote:
 Originally Posted by Kees I get to 35 too as upperbound but I would be surprised if there were a configuration where 35 moves are actually needed
If 25 swaps are needed to make the top half all even/odd, then
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

2007-11-14, 16:34   #9
davieddy

"Lucan"
Dec 2006
England

2×3×13×83 Posts

Quote:
 Originally Posted by axn1 The 10 swaps of the even "boundary" values can be avoided if we swap just the odds using the formula 99-
Slight quibbles:
What if <even counterpart> is 100?
What if 99 - <even counterpart> lies in the boundary?

2007-11-14, 17:56   #10
Wacky

Jun 2003
The Texas Hill Country

100010000012 Posts

Quote:
 Originally Posted by davieddy Slight quibbles: What if 99 - lies in the boundary?
Go on and swap it. In its present location, it will need to be swapped with the "correct" replacement anyway. That swap can use the token in the current position just as well.

2007-11-14, 18:09   #11
Wacky

Jun 2003
The Texas Hill Country

44116 Posts

Quote:
 Originally Posted by davieddy Slight quibbles: What if is 100?
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 2007-11-14 at 20:21 Reason: Clarify that I was referring to only the tokens on the "odd" side

 Similar Threads Thread Thread Starter Forum Replies Last Post S485122 Data 50 2011-01-10 10:28 tichy Math 1 2010-12-23 16:47 Carl Fischbach Miscellaneous Math 8 2010-07-02 08:03 Shaopu Lin Factoring 2 2004-10-31 13:48 Kevin Puzzles 4 2003-07-27 01:11

All times are UTC. The time now is 12:22.

Sat Dec 5 12:22:54 UTC 2020 up 2 days, 8:34, 0 users, load averages: 1.58, 1.50, 1.63