## A proof that c_5=154 (?)

After two failed attempts at constructing a line-free 154-element pattern, here is another one which finally seems to work, but requires independent checking:

This represents ${}[3]^5$, where all red and blue squares are not in the set (the red ones being removed in a second run after making sure all blue ones are removing as many lines as possible). The bottom left blue square is 11111, the white one just at its right is 11112, and so on. It seems that all horizontal, vertical, and diagonal lines are indeed prohibited in the end.

Count: $3\times (9\times 6) -2-3-3=3\times 54-8=162-8=154$. Then, using Michael’s proof that $c_5<155$, one concludes that $c_5=154$.

I hope somebody will be able to confirm it here. If not, those interested by that method might want to discuss it here without bothering the main 700 thread.

If anything works out then we’d update the wiki, and have a look at $c_6$ to see if some explicit formulation for general $c_n$ can be inferred.

This new pattern above has a lot of permutations into it and as such makes at least more sense that the previous flawed ones.

Edit:
Thanks for the replies, corrections included in green below.

New edit: a few more corrections in green, total count is at 150 now.

Edit: it seems that Terry’s line and another one can both be removed at once by doing some changes.

Unrelatedly another 3 lines were forgotten, so total at 148 now, not even as good as the lower bound by other methods.

Edit: I’m posting a follow-up here: a new programming strategy.

Advertisements

Tags:

### 11 Responses to “A proof that c_5=154 (?)”

1. Terence Tao Says:

Hi; you may wish to add the polymath1 tag to this post.

I think I see a line on the middle row of 9 ${} [3]^2$s, using the middle left square of the leftmost ${} [3]^2$ of this row, the centre of the middle ${} [3]^2$ in this row, and the middle right square of the rightmost ${} [3]^2$ row.

It might be worthwhile to have some sort of script or applet that can input a ${}[3]^5$ candidate and identify all of its lines. One could imagine a “minesweeper” like “game” using the above “board”.

[tag added, LaTeX edited — Tom.]

2. Sune Kristian Jakobsen Says:

Isn’t *1**3 a line in the set?

3. Thomas Sauvaget Says:

Thank you for the comments!

Terry: yes you’re right I see that line now (in the corrected pattern it is killed with a green square).

I agree this should really be automated, I’ll try to look into that.

Sune: thanks, I didn’t catch that one either. Now also fixed with a green square.

4. Sune Kristian Jakobsen Says:

*3*3* and 2*1** seems to be two other disjoint lines in the set.

5. Thomas Sauvaget Says:

Yet a couple more lines removed, now total of 150 so this won’t improve the lower bound in any case. 😦

Some programming do be done later then…

6. Thomas Sauvaget Says:

Maybe something can still be salvaged: by removing two lines differently I get 151, see above.

7. Sune Kristian Jakobsen Says:

2*1** and 3*1** still is in the set.

8. Thomas Sauvaget Says:

Ooops, just spotted *3*32, back to 150, see above.

9. Thomas Sauvaget Says:

Sune: yes thanks very much, sorry about that, now I see 2*1**, just removed it, and the other too.

Total 148 then, not even as good as the lower bound!

I’ll try to automate it, for the moment this method doesn’t cut the mustard at all…

10. a new strategy for computing c_n « Azur, sciences & arts Says:

[…] Azur, sciences & arts « A proof that c_5=154 (?) […]

11. Visualizing solutions I « The Twofold Gaze Says:

[…] I spent some time writing a routine to display solutions.   It’s based on this system.   Here are three extremals of length 353 for […]