Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Distinct Islands in the Matrix

  1. Jul 25, 2004 #1
    1>Given a nxn grid , we colour the grid with 2 colours such that we get the maximum number of distinct islands. What is the maximum number of distinct islands possible for a given nxn grid?
    *
    2>For 3-colours?
    *
    3>Is generalisation possible to m-colours??
    *
    [clarification]
    given a 3x3 grid and 2 colours then this colouration *
    *
    1||2||1
    --------
    2||2||2
    --------
    1||2||1
    *
    gives us 5 islands (the 4 1's and the 1 group of 2's)
    *
    We consider horizontal adjacency,vertical adjacency and also diagonal adjacency when grouping to get islands.
    [/clarification]
    *
     
  2. jcsd
  3. Aug 4, 2004 #2
    has anyone had any progress on this??

    All i could judge abt this question was that it was remotely equivalent to the kings problem so the answer must be very much similar. Though a rigorous proof would take the meat!

    -- AI
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?