7
\$\begingroup\$

A special case of Ramsey's theorem says the following: whenever we color the edges of the complete graph on 18 vertices red and blue, there is a monochromatic clique of size 4.

In language that avoids graph theory: suppose we place 18 points around a circle and draw all possible line segments connecting them in one of two colors: either red or blue. No matter how this is done, it's always possible to choose 4 of the points such that all 6 line segments between them are the same color: either all 6 are red or all 6 are blue.

Moreover, 18 is the least number for which this will work. For 17 points, we can color the line segments so that it's impossible to choose 4 points in this way.

Your goal is to print one such coloring. Your output must be a 17 by 17 adjacency matrix in which the (i,j) entry gives the color of the line segment joining points i and j. It must be in a format such as the one below:

  R R B R B B B R R B B B R B R R
R   R R B R B B B R R B B B R B R
R R   R R B R B B B R R B B B R B
B R R   R R B R B B B R R B B B R
R B R R   R R B R B B B R R B B B
B R B R R   R R B R B B B R R B B
B B R B R R   R R B R B B B R R B
B B B R B R R   R R B R B B B R R
R B B B R B R R   R R B R B B B R
R R B B B R B R R   R R B R B B B
B R R B B B R B R R   R R B R B B
B B R R B B B R B R R   R R B R B
B B B R R B B B R B R R   R R B R
R B B B R R B B B R B R R   R R B
B R B B B R R B B B R B R R   R R
R B R B B B R R B B B R B R R   R
R R B R B B B R R B B B R B R R  

The exact output above represents a valid coloring, so it is perfectly acceptable. But you have the following additional freedom to do something else:

  • You may print the adjacency matrix for any graph that satisfies the Ramsey condition, not just this one. (For example, any permutation of the rows with a corresponding permutation of the columns gives another acceptable output. I haven't checked if any non-isomorphic colorings exist.)
  • You may use any two distinct, non-whitespace characters in place of R and B to represent the two colors.

However, the spacing must appear exactly as in the example above: a space between cells in the same row, spaces in the diagonal entries, and newlines after each row. Leading and trailing spaces and newlines are allowed (but the entries of the adjacency matrix should be aligned with each other).

This is , so the shortest code in bytes wins. Because this is , hardcoding the output is allowed. Otherwise, standard loopholes apply.

\$\endgroup\$
  • \$\begingroup\$ Did I do it right? \$\endgroup\$ – Magic Octopus Urn Nov 2 '17 at 22:04
  • \$\begingroup\$ Sure looks like it to me. \$\endgroup\$ – Misha Lavrov Nov 2 '17 at 22:05
3
\$\begingroup\$

Jelly, 12 bytes

“ḍ⁾’B⁶;ṙJ$ṚG

Try it online!

How it works

“ḍ⁾’B⁶;ṙJ$UG  Main link. No arguments.

“ḍ⁾’          Set the return value to 53643.
    B         Binary; yield [1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1].
     ⁶;       Prepend a space, yielding [' ',1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1].
         $    Monadic chain:
        J       Yield all indices of the array, i.e., [1, ..., 17].
       ṙ        Rotate the array 1, ..., 17 units to the left, yielding a matrix.
          Ṛ   Reverse the order of the rows.
           G  Format the matrix as a grid.
\$\endgroup\$
4
\$\begingroup\$

Python 3, 56 bytes

s=' '+bin(53643)[2:]
for _ in s:print(*s);s=s[-1]+s[:-1]

Try it online!


Python 3, 56 bytes

s=' 1101000110001011'*16
while s:print(*s[:17]);s=s[16:]

Try it online!


Python 2, 64 bytes

for k in range(289):print'\n'[k%17:]+' ab'[(k/17-k%17)**8%17%7],

Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 18 bytes

18G•Ó₆•bð«NFÁ}Sðý=

Try it online!


Uses 1 for R and 0 for B.

\$\endgroup\$
2
\$\begingroup\$

Ruby, 53 bytes

17.times{|i|puts (" %b"%53643*99).chars[i*16,17]*' '}

Try it online!

Ruby, 58 bytes

289.times{|i|$><<(" %b"%53643)[-i*16/17%17]+" 
"[i%17/16]}
\$\endgroup\$
1
\$\begingroup\$

J, 30 bytes

(-+:i.17)|."0 1'   ',":#:53643

Explanation

                          #: - converts the number to a list of binary digits
                       ":    - converts the list to a string
                '   ',       - prepends 3 spaces in front of the string
         |."0 1              - rotates the list (rank 0 1) 
(-+:i.17)                    - offset for the 0, 2, 4... 32 rotations 

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Shouldn't the input of 53643 be included in the byte count? \$\endgroup\$ – Misha Lavrov Nov 3 '17 at 15:37
  • \$\begingroup\$ @Misha Lavrov My first solution had the number integrated. OK, I'll revert to it. \$\endgroup\$ – Galen Ivanov Nov 3 '17 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.