mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-11-13, 15:22   #1
Kees
 
Kees's Avatar
 
Dec 2005

3×5×13 Posts
Default 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
Kees is offline   Reply With Quote
Old 2007-11-13, 15:33   #2
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

43×103 Posts
Default

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?
petrw1 is offline   Reply With Quote
Old 2007-11-13, 15:48   #3
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default

Quote:
Originally Posted by petrw1 View Post
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
davieddy is offline   Reply With Quote
Old 2007-11-13, 16:01   #4
Kees
 
Kees's Avatar
 
Dec 2005

110000112 Posts
Default

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
Kees is offline   Reply With Quote
Old 2007-11-14, 02:02   #5
davar55
 
davar55's Avatar
 
May 2004
New York City

2×2,099 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
Old 2007-11-14, 03:52   #6
axn
 
axn's Avatar
 
Jun 2003

4,723 Posts
Default

The 10 swaps of the even "boundary" values can be avoided if we swap just the odds using the formula 99-<even counterpart>
axn is offline   Reply With Quote
Old 2007-11-14, 07:23   #7
Kees
 
Kees's Avatar
 
Dec 2005

3·5·13 Posts
Default

I get to 35 too as upperbound but I would be surprised if there were a configuration where 35 moves are actually needed
Kees is offline   Reply With Quote
Old 2007-11-14, 16:01   #8
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

193316 Posts
Default

Quote:
Originally Posted by Kees View Post
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 is offline   Reply With Quote
Old 2007-11-14, 16:34   #9
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default

Quote:
Originally Posted by axn1 View Post
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?
davieddy is offline   Reply With Quote
Old 2007-11-14, 17:56   #10
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

2·541 Posts
Default

Quote:
Originally Posted by davieddy View Post
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 is offline   Reply With Quote
Old 2007-11-14, 18:09   #11
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

2×541 Posts
Default

Quote:
Originally Posted by davieddy View Post
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"

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
is M21934219 composite ? S485122 Data 50 2011-01-10 10:28
S_N cycles in LL done on composite M(p) tichy Math 1 2010-12-23 16:47
The composite conjecture Carl Fischbach Miscellaneous Math 8 2010-07-02 08:03
F10,21=10^(2^21)+1 is composite Shaopu Lin Factoring 2 2004-10-31 13:48
Checkerboard Problem Kevin Puzzles 4 2003-07-27 01:11

All times are UTC. The time now is 10:35.

Sat Oct 31 10:35:49 UTC 2020 up 51 days, 7:46, 2 users, load averages: 1.95, 1.96, 1.91

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.