Composite checkerboard

[Kees]

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

[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?

[davieddy]

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

[Kees]

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

[davar55]

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.

[axn]

The 10 swaps of the even "boundary" values can be avoided if we swap just the odds using the formula 99-<even counterpart>

[Kees]

I get to 35 too as upperbound but I would be surprised if there were a configuration where 35 moves are actually needed

[davieddy]

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

[davieddy]

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-<even counterpart>

Slight quibbles:
What if <even counterpart> is 100?
What if 99 - <even counterpart> lies in the boundary?

[Wacky]

Originally Posted by davieddy

Slight quibbles:
What if 99 - <even counterpart> 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.

[Wacky]

Originally Posted by davieddy

Slight quibbles:
What if <even counterpart> 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"