27 spaces

[alerosa]

There are 27 spaces that need to be filled with a one-digit number each. Each number from 1 to 9 must be used exactly three times, following this one rule:

- Between the spaces which contain the number X, there must be X spaces containing other numbers. For example:

1 _ 1 _ 1 _ 2 _ _ 2 _ 3 2 _ _ 3 _ _ _ 3 _ _ _ _ _ _ _

In the above example, between the first "1" and the second "1", there is one space. Between the second "1" and the third "1", there is one space. Between the first "2" and the second "2", there are two spaces. Between the second "2" and the third "2", there are two spaces, and so on...

In the end, all 27 spaces must be filled in with a number from 1 through 9, each number must appear exactly 3 times, and the rule explained above must be respected.

Can you prove there is a solution to this? If so, can you find this solution?

[phil1882]

i cheated and worte a program to solve it.

[1, 9, 1, 6, 1, 8, 2, 5, 7, 2, 6, 9, 2, 5, 8, 4, 7, 6, 3, 5, 4, 9, 3, 8, 7, 4, 3]

[1, 9, 1, 2, 1, 8, 2, 4, 6, 2, 7, 9, 4, 5, 8, 6, 3, 4, 7, 5, 3, 9, 6, 8, 3, 5, 7]

[1, 8, 1, 9, 1, 5, 2, 6, 7, 2, 8, 5, 2, 9, 6, 4, 7, 5, 3, 8, 4, 6, 3, 9, 7, 4, 3]

[alerosa]

Phil, this was passed down to me by a teacher in my senior year in high school (I live in Brazil btw ). No one got it then. I've solved it using C, then later using Excel's Solver. Couldn't do it "elegantly", though.

An approach I thought of was to convert the problem to binary numbers. I created 9 variables (x1, x2, ..., x9) which represented the 1st space in which a digit would appear. So if x3 = 6, then the 1st "3" would appear in the sixth space. I then represented each digit the following way (binary):

1 - 10101 = 2^0 + 2^2 + 2^4 = 1+4+16 = 21

2 - 1001001= 2^0 + 2^3 + 2^6 = 1 + 8 + 64 = 73

3 - 100010001 = ... ...

9 - 100000000010000000001 = ...

However, I do not initially know where any number is going to be. What I do know is that there are 27 spaces, and that there will be a certain number of "0"s after each binary. For instance, if I knew the 1st space had "1" on it, I'd have 10101 followed by 22 "0"s. This would make the binary equal to 2^22 * 21, because adding a 0 to the end of a binary number just means the number is multiplied by 2. The formula I would now have to solve is: 2^(22-x1+1)*21 + 2^(20-x2+1)*73 + .... = 2^0 + 2^1 + ... + 2^26

Couldn't get any further than this hahahaha, don't even know if this helps at all!

Edited July 17, 2012 by alerosa

[phil1882]

yeah i basically wrote a trial and error program.

#python program

def placement(n,a):

    if n == 0;

	   print(a)

	   return True

    check = False

    for i in range(0,len(a)-(2*n+2)):

	   if a[i] == 0 and a[i+n+1] == 0 and a[i+2*n+2] == 0:

		  copy =a[:]

		  copy[i], copy[i+n+1], copy[i+2*n+2] = n,n,n

		  check = placement(n-1,copy)

    return check


array = [0]*27

placement(9,array)

[alerosa]

Hahaha I have no idea how that code works, but looks a MILLION times easier and smarter than what i did in C; mine had like 100 lines or something. Still wondering if there is a smart way to do this.

[phil1882]

to put it simply it does the following:

try 9 in the first position that works. try 8 in the first position that works; and so on.

if at any point a number doesn't work in the current position, ie. no available legal spots, it will back track and try again.

[hhh3]

to put it simply it does the following:

try 9 in the first position that works. try 8 in the first position that works; and so on.

if at any point a number doesn't work in the current position, ie. no available legal spots, it will back track and try again.

ha ha... i tried to do the same... but with pen and paper... well.. not so surprisingly, no result yet....

Edited July 19, 2012 by hhh3