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

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?

[quote=petrw1;118371]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?[/quote]

I think the answers are clearly:
1. No
2. No
3. Yes

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

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.

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

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

[quote=Kees;118425]I get to 35 too as upperbound but I would be surprised if there were a configuration where 35 moves are actually needed[/quote]
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

[quote=axn1;118417]The 10 swaps of the even "boundary" values can be avoided if we swap just the odds using the formula 99-<even counterpart>[/quote]
Slight quibbles:
What if <even counterpart> is 100?
What if 99 - <even counterpart> lies in the boundary?

[QUOTE=davieddy;118452]Slight quibbles:
What if 99 - <even counterpart> lies in the boundary?[/QUOTE]

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.

[QUOTE=davieddy;118452]Slight quibbles:
What if <even counterpart> is 100?[/QUOTE]

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"

[quote=davieddy;118448]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.
[/quote]

It's possible that all twenty-five swaps needed will be "behind the lines"
and not on the boundary (which may be evens and odds already).
In that case all 35 swaps may be needed to get the composite
configuration desired.
It's still open as to whether separating into even/odd halves
is in fact optimal.

[quote=davar55;118466]It's possible that all twenty-five swaps needed will be "behind the lines"
and not on the boundary (which may be evens and odds already).
[/quote]
In that case you can elect to make the top half all odd instead of
all even (or vice versa), thereby having to swap all the boundary pieces
in the first 25 swaps..

[quote=Wacky;118460]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.[/quote]
Yes. Since all the even counterparts are distinct, so is
99-<even counterpart> mod 100. So there is no contention for
the same number along the odd boundary.

Yes I made a booboo.
Maybe 199 is prime or maybe it isn't.
But if you dont want to talk to me,
I don't want to talk to you.

David