Results 1 to 13 of 13

Thread: Question on a puzzle

  1. #1
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,671
    Thanks
    313

    Question on a puzzle

    Concerns the current puzzle here (Chess Codes):
    PUZZLEUP - Weekly Puzzle Competition (a problem and games site)

    Seems to me it can be worded this way:
    .................................................. ...........

    An 8by8 array is filled at random with numbers 1 to 64.

    A "move" consists of swapping an odd with an even number.

    The aim is to end up with:

    01 02 03 04 05 06 07 08
    16 15 14 13 12 11 10 09
    .....
    49 50 51 52 53 54 55 56
    64 63 62 61 60 59 58 57

    Minimum moves = ?
    .................................................. ...........
    Any comments? Thank you.
    Not looking for solution...only if I interpreted correctly.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,815
    Thanks
    588

    Re: Question on a puzzle

    Your formulation is different, Denis. You are using odd/even to represent the colour of the square (black/white), but that means that you swap the colours as well as the codes. In the original problem the colours are attached to the squares, not the codes.

    I think, Romsek, that the target is to find the maximum, over all starting positions, of the minimum number of moves required. So one inefficient way to proceed would be to find, for each possible start position, the minimum number of moves required and then find the greatest of each of those numbers.
    Last edited by Archie; Nov 24th 2016 at 09:37 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,671
    Thanks
    313

    Re: Question on a puzzle

    Thanks Archie; I see the fault in my assumption;
    but easier to use as "code numbers"...less typing!

    What I assumed is equivalent to saying you can swap
    any number in an odd position with any number in an
    even position....a goof!

    Of course, worst case is where all odd numbers are in even
    positions and all even numbers are in odd positions.

    You mention Romsek: where d'hell is he?!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,815
    Thanks
    588

    Re: Question on a puzzle

    He obviously thought better of a comment about what number we were looking for. I didn't know we could delete posts here.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,041
    Thanks
    698
    Awards
    1

    Re: Question on a puzzle

    Quote Originally Posted by Archie View Post
    I didn't know we could delete posts here.
    Yeah but I can see all of them regardless, so behave.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,671
    Thanks
    313

    Re: Question on a puzzle

    I think solution is 64 or 65. How bout you Archie/Romsek?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,815
    Thanks
    588

    Re: Question on a puzzle

    If every piece is on the right colour but the wrong square you need at least 64 swaps to get them right. The question is whether you can guarantee that the first set of swaps leaves every piece such that the square it is now on belongs to the piece that is now on it's own square.

    You can consider each arrangement to consist of a number of cycles a \to b \to c \to d \to \ldots \to a such that a is on b's square, b is on c's square, etc.. Can we guarantee to break all those cycles into 2-cycles such that each 2-cycle contains one black square and one white?
    Last edited by Archie; Nov 24th 2016 at 04:55 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,815
    Thanks
    588

    Re: Question on a puzzle

    For an n piece problem:
    • if there is an even on an odd square, the pigeonhole principle says that there is also an odd on an even square. We can move both pieces home in 2 moves (at most) reducing the problem to an n-2 piece problem.
    • if there is no even on an odd square, there is also no odd on an even. We can swap any even with any odd and then apply the previous case.

    Thus \max{(2n)} \le 3+\max{(2n-2)}. And \max{(2)}=1. We therefore have \max{(2n)} \le 3n-2 and \max{(64)} \le 94

    But, I think that, if we have no even on odd with n pieces, then when we make the three moves to get to the (2n-2) case, parity dictates that we now have a one even on odd and one odd on even.

    Thus \max{(2n)} \le 5+\max{(2n-4)}. And \max{(4)}=4. We therefore have \max{(4n)} \le 5n-1 and \max{(64)} \le 79
    Last edited by Archie; Nov 24th 2016 at 06:43 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,815
    Thanks
    588

    Re: Question on a puzzle

    But since had only 1 odd on even and only 1 even on odd, there are only two possible cases.

    Either they are on each other's squares or the are not. If they are, it takes only one change to take two more from the size of the puzzle in which case we are back to no odd on even and no even on odd. Or, the odd, being the only odd on even must swap with another odd to get home and the even must swap with an even. In either case we get \max{(2n)} \le 4+\max{(2n-4)} and so \max{(4n)} \le 4n and \max{(64)} \le 64.

    Now we have 64 \le \max{(64)} \le 64 so

    \max{(64)} = 64
    Last edited by Archie; Nov 24th 2016 at 06:44 PM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,671
    Thanks
    313

    Re: Question on a puzzle

    Thanks Archie.
    Say instead we have a 2 by 4:
    you'd then expect 8 as answer; but 9 is needed.
    Seems to be because we're not dealing with a square.
    Is that correct?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,815
    Thanks
    588

    Re: Question on a puzzle

    I thought I had 8 for 8 (as I'd expect). What's your starting position that needs 9?

    For example:
    $$ 3\color{red}{4} 5\color{red}{6} 7\color{red}{8} 1\color{red}{2} \\ 3\color{red}{4} 5\color{red}{6} \color{blue}{8}\color{blue}{7} 1\color{red}{2} \\ 3\color{red}{4} 5\color{red}{6} \color{blue}{2}\color{red}{7} 1\color{blue}{8} \\ 3\color{red}{4} 5\color{red}{6} 2\color{blue}{1} \color{blue}{7}\color{red}{8} \\ \color{blue}1\color{red}{4} 5\color{red}{6} 2\color{blue}{3} 7\color{red}{8} \\ 1\color{blue}{2} 5\color{red}{6} \color{blue}{4}3 7\color{red}{8} \\ 1\color{red}{2} \color{blue}3\color{red}{6} 4\color{blue}{5} 7\color{red}{8} \\ 1\color{red}{2} 3\color{blue}{4} \color{blue}{6}5 7\color{red}{8} \\ 1\color{red}{2} 3\color{red}{4} \color{blue}{5}\color{blue}{6} 7\color{red}{8} $$
    Last edited by Archie; Nov 24th 2016 at 08:49 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,671
    Thanks
    313

    Re: Question on a puzzle

    (3, 4, 1, 6, 7, 8, 5, 2)
    (1,3) and (5,7) for the odds; and (2,4,6,8) for the evens.

    Also 9 needed if above is a 1 by 8.

    So seems answer = (2n)^2 if we're dealing with a 2n by 2n array.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,815
    Thanks
    588

    Re: Question on a puzzle

    I'm not convinced about that. I've missed a case in my analysis. Where there is one odd on even and one even on odd, you can have either the even is on the odd's square but not vice versa. Or you can have the odd on the even's square, but not vice-versa.

    This creates a problem that requires at least one additional move to unpick.

    Do we first have to join all the cycles and then start the process to reduce n? Or is it just a case of adjusting the parity at some point? But then the question is how and when?

    A quick application of my algorithm gave me 19 for (2, 3, 4, 1, 6, 7, 8, 5, A, D, C, 9, E, F, 0, D) where zero must come first in the ordered array. Whether that is optimal or not, I don't know.
    Last edited by Archie; Nov 24th 2016 at 09:32 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. One Puzzle
    Posted in the Math Puzzles Forum
    Replies: 13
    Last Post: May 21st 2014, 03:59 AM
  2. Puzzle like algebra question
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Apr 5th 2011, 06:50 AM
  3. A new puzzle?
    Posted in the Math Puzzles Forum
    Replies: 1
    Last Post: Oct 23rd 2010, 12:29 PM
  4. puzzle question of grade 6
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Apr 29th 2008, 01:47 AM
  5. a very trick/puzzle question!
    Posted in the Calculus Forum
    Replies: 0
    Last Post: Mar 17th 2008, 05:07 PM

/mathhelpforum @mathhelpforum