View Single Post
Old 2007-11-14, 02:02   #5
davar55
 
davar55's Avatar
 
May 2004
New York City

419810 Posts
Default

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.
davar55 is offline   Reply With Quote