You and four other people (who coincendentally are all smarties) are in late testing room where you will take your test where there is a 6 by 6 grid of equally spaced desks with chairs in the same relative spot.

You go into the room after all four smarties have chosen their location. You have a test taking policy where you always want to sit at the midpoint between two smarties. The smarties in the room with you feel the exact opposite way, so their arrangement is always such that no smartie is at the midpoint of two other smarties

However, depending on where the smarties are sitting, you may not be able to sit at the midpoint since in all cases it would always be where there is no chair and desk. (There is a strict no moving desks or chairs rule too.) How many ways could the current 4 smarties sit such that you couldn't sit at the midpoint of two smarties if reflections and rotations count as well?

How many ways could you not find where you want to sit if there were 5 smarties other than you and reflections and rotations count as well?

I would not divide by 24 as Jer did, as I assume that the four smarties are distinct individuals.  Anyhow here is how I got my solution:

----------------
public class Smarties {

  //grid given by pts (x,y), where 0<=x,y<6
  //pt (x,y) represented by integer 6x+y
  public static void main(String[] args) {
    int count = 0;

    for (int a=0; a<36; a++) {
      for (int b=a+1; b<36; b++) {
    for (int c=b+1; c<36; c++) {
      for (int d=c+1; d<36; d++) {
        if (valid(a,b,c,d)) {
          if (!midpointPossible(a,b,c,d)) count++;
    }}}}}

    System.out.println(count*24); //4!=24 orders
  }

  //no smartie at midpt of two other smarties
  private static boolean valid(int a, int b, int c, int d) {
    int x,y;
    int[][] pts;

    pts = new int[4][2];
    pts[0][0] = a/6; pts[0][1] = a%6;
    pts[1][0] = b/6; pts[1][1] = b%6;
    pts[2][0] = c/6; pts[2][1] = c%6;
    pts[3][0] = d/6; pts[3][1] = d%6;

    for (int i=0; i<4; i++) {
      for (int j=i+1; j<4; j++) {
    for (int k=j+1; k<4; k++) {
      if ((pts[i][0]+pts[k][0])%2==0) {
        if ((pts[i][1]+pts[k][1])%2==0) {
          x = (pts[i][0]+pts[k][0])/2;
          y = (pts[i][1]+pts[k][1])/2;
          if (x==pts[j][0] && y==pts[j][1]) return false;
    }}}}}

    return true;
  }

  //no midpt of two smarties available
  private static boolean midpointPossible(int a, int b, int c, int d) {
    int midpt,x,y;
    int[][] pts;

    pts = new int[4][2];
    pts[0][0] = a/6; pts[0][1] = a%6;
    pts[1][0] = b/6; pts[1][1] = b%6;
    pts[2][0] = c/6; pts[2][1] = c%6;
    pts[3][0] = d/6; pts[3][1] = d%6;

    for (int i=0; i<4; i++) {
      for (int j=i+1; j<4; j++) {
    if ((pts[i][0]+pts[j][0])%2==0) {
      if ((pts[i][1]+pts[j][1])%2==0) {
        x = (pts[i][0]+pts[j][0])/2;
        y = (pts[i][1]+pts[j][1])/2;
        midpt = 6*x+y;
        if (midpt!=a && midpt!=b && midpt!=c && midpt!=d) {
          return true;
    }}}}}
    return false;
  }
}

Posted by David Shin on 2004-11-05 14:38:07