Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Nov 24, 2013

Technical Interview Brain Teaser - IBM Ponder This - Neighbour Configuration

Source: IBM Ponder This Dec 12 ( http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/December2012.html ) - Mailed to me by Aashay Harlalka (Final Year Student, CSE, IITB)

Problem:

36 people live in a 6x6 grid, and each one of them lives in a separate square of the grid. Each resident's neighbors are those who live in the squares that have a common edge with that resident's square.

Each resident of the grid is assigned a natural number N, such that if a person receives some N>1, then he or she must also have neighbors that have been assigned all of the numbers 1,2,...,N-1.

Find a configuration of the 36 neighbors where the sum of their numbers is at least 90.

As an example, the highest sum we can get in a 3x3 grid is 20:
1 2 1
4 3 4
2 1 2

Update (24 June 2014):
Solution: Available on IBM Research Ponder This - December 2012 Solution

12 comments:

  1. 3,2,1,2,3,1
    1,5,3,4,5,2
    3,4,2,1,1,3
    2,1,1,3,4,2

    ReplyDelete
  2. I don't think one can go beyond 86.

    3,1,1,2,2,1
    2,5,4,3,5,1
    1,3,2,1,4,2
    2,4,1,2,3,1
    2,5,3,4,5,1
    1,1,2,1,2,3

    ReplyDelete
    Replies
    1. well u ar ealmost right but just in the last row first coloumn and first row last coloumn u just need to change the 1's to 3's and u will get the total to be 90

      Delete
    2. No, I can't do that because we need to have 1 in the neighbour of 2 (Second Last row, first column) and similarly at the other corner as well :-)
      But, the solution posted below is I think correct.

      Delete
  3. Well, I thing it could be this:
    1, 2, 2, 1, 3, 2
    3, 5, 4, 3, 2, 1
    2, 1, 1, 4, 5, 3
    3, 5, 4, 2, 1, 2
    1, 2, 3, 4, 5, 3
    2, 3, 1, 1, 2, 1

    ReplyDelete
  4. 1 2 3 2 3 1
    3 5 4 1 5 2
    2 1 2 2 4 3
    3 4 2 2 1 2
    2 5 1 4 5 3
    1 3 2 3 2 1

    ReplyDelete
    Replies
    1. The '3' in the 1st row and 3rd column has not a '1' nearby...

      Delete
  5. 1 2 1 3 4 1
    3 2 3 2 2 4
    3 1 4 3 1 3
    2 4 5 4 5 2
    1 3 4 1 3 1
    2 2 1 2 2 1

    ReplyDelete
  6. The '4' in the second last row, the '4' in between the two '5's and the '4' above one '5' do not have a '2' nearby..

    ReplyDelete
  7. 4 2 4 5 1 4
    1 3 1 3 2 3
    6 4 5 2 1 5
    2 5 6 3 4 6
    1 3 1 5 2 3
    4 2 3 4 1 4

    ReplyDelete
    Replies
    1. 2 in first row doesnot have a one nearby

      Delete
  8. As posted on http://domino.research.ibm.com/comm/wwwr_ponder.nsf/solutions/December2012.html

    A solution without 5 (sum = 90):

    2 4 1 4 2 1
    1 3 2 3 4 1
    2 4 4 1 4 2
    4 1 3 2 3 4
    3 2 4 4 1 1
    1 3 1 3 2 3

    Optimal solution of 93:

    1 3 2 3 1 3
    2 5 1 4 5 2
    3 4 1 2 3 1
    1 2 3 5 4 1
    3 5 4 1 2 3
    2 1 2 3 4 1

    Thanks

    ReplyDelete