Results 1 to 3 of 3

Math Help - Sliding jigsaw configurations

  1. #1
    Member
    Joined
    May 2009
    Posts
    146

    Sliding jigsaw configurations

    Consider an N\times N sliding jigsaw (SJ) with an empty block and {N}^{2}-1 numbered blocks from 1 to {N}^{2}-1 (see the attachment for a configuration of a 4 \times 4 SJ, where blocks 8,5,2 or 9 can move to the empty block, leaving their blocks empty, which any of their adjacent neighbors can in turn move to, ect.)

    Definition 1: A configuration is standard, if the empty block is at the northwest corner of the board.

    Definition 2: A configuration is ordered, if every block is greater than the block to its left (the first block of a row is greater than the last block of the previous row), ignoring the empty block.

    Question 1: Starting from a standard configuration of an N\times N SJ, how many different standard configurations can we reach?

    Question 2: Starting from an arbitary configuration, can we reach an ordered SJ?
    Attached Thumbnails Attached Thumbnails Sliding jigsaw configurations-jigsaw.jpg  
    Last edited by godelproof; July 26th 2011 at 04:38 AM. Reason: attachment added
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7

    Re: Sliding jigsaw configurations

    There is a very clear analysis of the 4x4 case here, with enough information to give you some good hints on tackling the NxN case.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2009
    Posts
    146

    Re: Sliding jigsaw configurations

    Thanks. So answer is:

    Q1: ({N}^{2}-1)!/2

    Q2: Yes.

    Right?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: November 16th 2011, 04:44 AM
  2. Replies: 6
    Last Post: January 12th 2011, 12:45 PM
  3. Sliding ladder problem
    Posted in the Calculus Forum
    Replies: 2
    Last Post: July 31st 2010, 07:22 PM
  4. Calculating probable configurations
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: October 20th 2008, 12:02 AM
  5. friction and sliding box
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 26th 2007, 11:46 PM

Search Tags


/mathhelpforum @mathhelpforum