Ramsey's theorem: Difference between revisions

Content added Content deleted

Inline

Revision as of 11:34, 20 April 2014

The task is to find a graph with 17 Nodes such that any 4 Nodes are neither totally connected nor totally unconnected, so demonstrating Ramsey's theorem. A specially-nominated solution may be used, but if so it must be checked to see if if there are any sub-graphs that are totally connected or totally unconnected.

C

This example is incorrect. Please fix the code and remove this message.

For 17 nodes, (4,4) happens to have a special solution: arrange nodes on a circle, and connect all pairs with distances 1, 2, 4, and 8. It's easier to prove it on paper and just show the result than let a computer find it (you can call it optimization). <lang c>#include <stdio.h>

int main() { int a[17][17] = Template:0; int i, j, k; const char *mark = "01-";

for (i = 0; i < 17; i++) a[i][i] = 2;

for (k = 1; k <= 8; k <<= 1) { for (i = 0; i < 17; i++) { j = (i + k) % 17; a[i][j] = a[j][i] = 1; } }

for (i = 0; i < 17; i++) { for (j = 0; j < 17; j++) printf("%c ", mark[a[i][j]]); putchar('\n'); } return 0; }</lang>

Output:

(17 x 17 connectivity matrix)

- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 
1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 
1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 
0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 
1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 
0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 
0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 
0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 
1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 
1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 
0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 
0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 
0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 
1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 
0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -

D

This example is incorrect. Please fix the code and remove this message.

Translation of: C

<lang d>import std.stdio;

void main() {

   enum size_t N = 17;
   char[N][N] mat = '0';

   foreach (immutable i, ref row; mat)
       row[i] = '-';

   foreach (immutable e; 0 .. 4) {
       foreach (immutable i, ref row; mat) {
           immutable j = (i + (2 ^^ e)) % N;
           row[j] = mat[j][i] = '1';
       }
   }

   writefln("%(%(%c %)\n%)", mat);

}</lang>

Output:

- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1
1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0
0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1
1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0
0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0
0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0
0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1
1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1
1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0
0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0
0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0
0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1
1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0
0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -

Erlang

This example is incorrect. Please fix the code and remove this message.

Translation of: C

Library: Erlang digraph

<lang erlang>-module(ramsey_theorem). -export([main/0]).

main() -> G = digraph:new([cyclic]), List = lists:seq(0,16), [digraph:add_vertex(G,V) || V <- List], [begin J = ((I + K) rem 17), digraph:add_edge(G, I, J), digraph:add_edge(G, J, I) end || I <- List, K <- [1,2,4,8]], Edges = [{V1,V2} || V1 <- digraph:vertices(G), V2 <- digraph:out_neighbours(G, V1)], Connectivity_matrix = lists:flatten( [[ [case I of J -> $-; _ -> case lists:member({I,J},Edges) of true -> $1; false -> $0 end end,$ ] || I <- List] ++ [$\n] || J <- List]), io:format("~s",[Connectivity_matrix]).</lang>

Output:

- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 
1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 
1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 
0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 
1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 
0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 
0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 
0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 
1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 
1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 
0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 
0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 
0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 
1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 
0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -

J

This example is incorrect. Please fix the code and remove this message.

Interpreting this task as "reproduce the output of all the other examples", then here's a stroll to the goal through the J interpreter: <lang j> i.@<.&.(2&^.) N =: 17 NB. Count to N by powers of 2 1 2 4 8

  1 #~ 1 j. 0 _1:} i.@<.&.(2&^.) N =: 17                          NB.  Turn indices into bit mask

1 0 1 0 0 1 0 0 0 0 1

  (, |.) 1 #~ 1 j. 0 _1:} i.@<.&.(2&^.) N =: 17                   NB.  Cat the bitmask with its own reflection

1 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1

  _1 |.^:(<N) _ , (, |.) 1 #~ 1 j. 0 _1:} <: i.@<.&.(2&^.) N=:17  NB.  Then rotate N times to produce the array

_ 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _

  NB. Packaged up as a re-usable function
  ramsey =: _1&|.^:((<@])`(_ , [: (, |.) 1 #~ 1 j. 0 _1:} [: <: i.@<.&.(2&^.)@])) 

  ramsey 17

_ 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _</lang> Yes, this is really how you solve problems in J.

Mathematica

This example may be incorrect.

The task has been changed to also require demonstrating that the graph is a solution.

Please verify it and remove this message. If the example does not match the requirements or does not work, replace this message with Template:incorrect or fix the code yourself.

<lang mathematica>CirculantGraph[17, {1, 2, 4, 8}]</lang>

Mathprog

Some lines in this example are too long (more than 80 characters). Please fix the code if it's possible and remove this message.

<lang>/*Ramsey 4 4 17

 This model finds a graph with 17 Nodes such that no clique of 4 Nodes is either fully
 connected, nor fully disconnected

 Nigel_Galloway
 January 18th., 2012

/

param Nodes := 17; var Arc{1..Nodes, 1..Nodes}, binary;

clique{a in 1..(Nodes-3), b in (a+1)..(Nodes-2), c in (b+1)..(Nodes-1), d in (c+1)..Nodes} : 1 <= Arc[a,b] + Arc[a,c] + Arc[a,d] + Arc[b,c] + Arc[b,d] + Arc[c,d] <= 5;

end;</lang>

This may be run with: <lang bash>glpsol --minisat --math R_4_4_17.mprog --output R_4_4_17.sol</lang> The solution may be viewed on this page. In the solution file, the first section identifies the number of nodes connected in this clique. In the second part of the solution, the status of each arc in the graph (connected=1, unconnected=0) is shown.

PARI/GP

This example is incorrect. Please fix the code and remove this message.

This takes the C solution to its logical extreme. <lang parigp>matrix(17,17,x,y,my(t=(x-y)%17);t==2^min(valuation(t,2),3))</lang>

Perl 6

This example is incorrect. Please fix the code and remove this message.

Translation of: C

<lang Perl 6>my @a = [ 0 xx 17 ] xx 17; @a[$_][$_] = 2 for ^17;

loop (my $k = 1; $k <= 8; $k +<= 1) {

   for ^17 -> $i {
       my $j = ($i + $k) % 17;
       @a[$i][$j] = @a[$j][$i] = 1;
   }

}

say <0 1 ->[@a[$_][]] for ^17;</lang>

Python

This example is incorrect. Please fix the code and remove this message.

<lang python>if __name__ == '__main__':

   range17 =  range(17)
   a = [['0'] * 17 for i in range17]
   for i in range17:
       a[i][i] = '-'
   for k in range(4):
       for i in range17:
           j = (i + pow(2, k)) % 17
           a[i][j] = a[j][i] = '1'
   for row in a:
       print(' '.join(row))</lang>

Output same as C:

Racket

This example is incorrect. Please fix the code and remove this message.

Kind of a translation of C (ie, reducing this problem to generating a printout of a specific matrix). <lang racket>#lang racket

(define N 17)

(define (dist i j)

 (define d (abs (- i j)))
 (if (<= d (quotient N 2)) d (- N d)))

(define v

 (build-vector N
   (λ(i) (build-vector N
           (λ(j) (case (dist i j) [(0) '-] [(1 2 4 8) 1] [else 0]))))))

(for ([row v]) (displayln row))</lang>

REXX

This example is incorrect. Please fix the code and remove this message.

Translation of: C

<lang rexx>/*REXX programs finds and displays a 17 node graph such that any four */ /*────── nodes are neither totally connected nor totally unconnected.*/ @.=0 /*initialize the node graph to 0.*/

    do d=0  for 17;  @.d.d=2;  end    /*set the diagonal elements to 2.*/

k=1

    do while k<=8
                   do i=0  for 17     /*process each column in array.  */
                   j= (i+k) // 17     /*set a  row,col  and  col,row.  */
                   @.i.j=1;  @.j.i=1  /*set two array elements to one. */
                   end   /*i*/
    k=k*2                             /*double the value of K each loop*/
    end   /*while k≤8*/

 do r=0  for 17; _=;  do c=0  for 17  /*show each row, build col by col*/
                      _=_ @.r.c       /*add this column to the row.    */
                      end   /*c*/

 say left(,9) translate(_,'-',2)    /*display the constructed row.   */
 end   /*r*/
                                      /*stick a fork in it, we're done.*/</lang>

Output:

(17x17 connectivity matrix):

           - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
           1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1
           1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0
           0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1
           1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0
           0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0
           0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0
           0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1
           1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1
           1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0
           0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0
           0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0
           0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1
           1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0
           0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1
           1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1
           1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -

Ruby

This example is incorrect. Please fix the code and remove this message.

<lang ruby>a = Array.new(17){['0'] * 17} 17.times{|i| a[i][i] = '-'} 4.times do |k|

 17.times do |i|
   j = (i + 2 ** k) % 17
   a[i][j] = a[j][i] = '1'
 end

end a.each {|row| puts row.join(' ')}</lang>

Output:

- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1
1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0
0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1
1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0
0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0
0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0
0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1
1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1
1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0
0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0
0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0
0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1
1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0
0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -

Run BASIC

This example is incorrect. Please fix the code and remove this message.

<lang runbasic>dim a(17,17) for i = 1 to 17: a(i,i) = -1: next i k = 1 while k <= 8

 for i = 1 to 17
   j = (i + k) mod 17
   a(i,j) = 1
   a(j,i) = 1
 next i
 k = k * 2

wend for i = 1 to 17

 for j = 1 to 17
   print a(i,j);" ";
 next j
 print

next i</lang>

-1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 
1 -1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 
1 1 -1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 
0 1 1 -1 1 1 0 1 0 0 0 1 1 0 0 0 1 
1 0 1 1 -1 1 1 0 1 0 0 0 1 1 0 0 0 
0 1 0 1 1 -1 1 1 0 1 0 0 0 1 1 0 0 
0 0 1 0 1 1 -1 1 1 0 1 0 0 0 1 1 0 
0 0 0 1 0 1 1 -1 1 1 0 1 0 0 0 1 1 
1 0 0 0 1 0 1 1 -1 1 1 0 1 0 0 0 0 
1 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 0 0 
0 1 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 0 
0 0 1 1 0 0 0 1 0 1 1 -1 1 1 0 1 0 
0 0 0 1 1 0 0 0 1 0 1 1 -1 1 1 0 0 
1 0 0 0 1 1 0 0 0 1 0 1 1 -1 1 1 0 
0 1 0 0 0 1 1 0 0 0 1 0 1 1 -1 1 0 
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -1 0 
1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 -1

Tcl

Works with: Tcl version 8.6

<lang tcl>package require Tcl 8.6

Generate the connectivity matrix

set init [split [format -%b 53643] ""] set matrix {} for {set r $init} {$r ni $matrix} {set r [concat [lindex $r end] [lrange $r 0 end-1]]} {

   lappend matrix $r

}

Check that every clique of four has at least *one* pair connected and one
pair unconnected. ASSUMES that the graph is symmetric.

proc ramseyCheck4 {matrix} {

   set N [llength $matrix]
   set connectivity [lrepeat 6 -]
   for {set a 0} {$a < $N} {incr a} {

for {set b 0} {$b < $N} {incr b} { if {$a==$b} continue lset connectivity 0 [lindex $matrix $a $b] for {set c 0} {$c < $N} {incr c} { if {$a==$c || $b==$c} continue lset connectivity 1 [lindex $matrix $a $c] lset connectivity 2 [lindex $matrix $b $c] for {set d 0} {$d < $N} {incr d} { if {$a==$d || $b==$d || $c==$d} continue lset connectivity 3 [lindex $matrix $a $d] lset connectivity 4 [lindex $matrix $b $d] lset connectivity 5 [lindex $matrix $c $d]

# We've extracted a meaningful subgraph; check its connectivity if {0 ni $connectivity} { puts "FAIL! Found wholly connected: $a $b $c $d" return } elseif {1 ni $connectivity} { puts "FAIL! Found wholly unconnected: $a $b $c $d" return } } } }

   }
   puts "Satisfies Ramsey condition"

}

puts [join $matrix \n] ramseyCheck4 $matrix</lang>

Output:

- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1
1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0
0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1
1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0
0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0
0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0
0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1
1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1
1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0
0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0
0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0
0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1
1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0
0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -
Satisfies Ramsey condition

@@ Line 3: / Line 3: @@
 =={{header|C}}==
+{{incorrect|C|The task has been changed to also require demonstrating that the graph is a solution.}}
 For 17 nodes, (4,4) happens to have a special solution: arrange nodes on a circle, and connect all pairs with distances 1, 2, 4, and 8.  It's easier to prove it on paper and just show the result than let a computer find it (you can call it optimization).
 <lang c>#include <stdio.h>
@@ Line 51: / Line 52: @@
 =={{header|D}}==
+{{incorrect|D|The task has been changed to also require demonstrating that the graph is a solution.}}
 {{trans|C}}
 <lang d>import std.stdio;
@@ Line 88: / Line 90: @@
 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1
 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -</pre>
 =={{header|Erlang}}==
+{{incorrect|Erlang|The task has been changed to also require demonstrating that the graph is a solution.}}
 {{trans|C}} {{libheader|Erlang digraph}}
 <lang erlang>-module(ramsey_theorem).
@@ Line 142: / Line 144: @@
 =={{header|J}}==
+{{incorrect|J|The task has been changed to also require demonstrating that the graph is a solution.}}
 Interpreting this task as "reproduce the output of all the other examples", then here's a stroll to the goal through the J interpreter: <lang j>   i.@<.&.(2&^.) N =: 17                                           NB.  Count to N by powers of 2
 2 4 8
@@ Line 188: / Line 190: @@
 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1 1
 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _ 1
-1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _</lang>  Yes, this is really how you solve problems in J.
+1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 _</lang>
+Yes, this is really how you solve problems in J.
 =={{header|Mathematica}}==
+{{needs-review|C|The task has been changed to also require demonstrating that the graph is a solution.}}
-<lang>CirculantGraph[17, {1, 2, 4, 8}]</lang>
+<lang mathematica>CirculantGraph[17, {1, 2, 4, 8}]</lang>
 [[File:Ramsey.png]]
 =={{header|Mathprog}}==
@@ Line 219: / Line 221: @@
 =={{header|PARI/GP}}==
+{{incorrect|PARI/GP|The task has been changed to also require demonstrating that the graph is a solution.}}
 This takes the [[#C|C]] solution to its logical extreme.
 <lang parigp>matrix(17,17,x,y,my(t=(x-y)%17);t==2^min(valuation(t,2),3))</lang>
 =={{header|Perl 6}}==
+{{incorrect|Perl 6|The task has been changed to also require demonstrating that the graph is a solution.}}
 {{trans|C}}
 <lang Perl 6>my @a = [ 0 xx 17 ] xx 17;
@@ Line 237: / Line 241: @@
 =={{header|Python}}==
+{{incorrect|Python|The task has been changed to also require demonstrating that the graph is a solution.}}
 <lang python>if __name__ == '__main__':
     range17 =  range(17)
@@ Line 248: / Line 253: @@
     for row in a:
         print(' '.join(row))</lang>
 {{out|Output same as C}}
 =={{header|Racket}}==
+{{incorrect|Racket|The task has been changed to also require demonstrating that the graph is a solution.}}
 Kind of a translation of C (ie, reducing this problem to generating a printout of a specific matrix).
-<lang racket>
+<lang racket>#lang racket
-#lang racket
 (define N 17)
@@ Line 267: / Line 271: @@
             (λ(j) (case (dist i j) [(0) '-] [(1 2 4 8) 1] [else 0]))))))
-(for ([row v]) (displayln row))
+(for ([row v]) (displayln row))</lang>
-</lang>
 =={{header|REXX}}==
+{{incorrect|REXX|The task has been changed to also require demonstrating that the graph is a solution.}}
 {{trans|C}}
 <lang rexx>/*REXX programs finds and displays a 17 node graph  such that  any four */
@@ Line 292: / Line 296: @@
   end   /*r*/
                                        /*stick a fork in it, we're done.*/</lang>
+{{out}}
-'''output''' <br><br>('''17x17''' connectivity matrix):
+('''17x17''' connectivity matrix):
 <pre style="overflow:scroll">
            - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1
@@ Line 314: / Line 319: @@
 =={{header|Ruby}}==
+{{incorrect|Ruby|The task has been changed to also require demonstrating that the graph is a solution.}}
 <lang ruby>a = Array.new(17){['0'] * 17}
 .times{|i| a[i][i] = '-'}
@@ Line 323: / Line 329: @@
 end
 a.each {|row| puts row.join(' ')}</lang>
 {{out}}
 <pre>
@@ Line 346: / Line 351: @@
 =={{header|Run BASIC}}==
+{{incorrect|Run BASIC|The task has been changed to also require demonstrating that the graph is a solution.}}
 <lang runbasic>dim a(17,17)
 for i = 1 to 17: a(i,i) = -1: next i
@@ Line 382: / Line 388: @@
 =={{header|Tcl}}==
-It is not enough merely to generate the graph; we should also ''show'' that the graph has the properties that we desire it to have.
 {{works with|Tcl|8.6}}
 <lang tcl>package require Tcl 8.6
@@ Line 389: / Line 394: @@
 set init [split [format -%b 53643] ""]
 set matrix {}
-for {set row $init} {$row ni $matrix} {set row [concat [lindex $row end] [lrange $row 0 end-1]]} {
+for {set r $init} {$r ni $matrix} {set r [concat [lindex $r end] [lrange $r 0 end-1]]} {
-    lappend matrix $row
+    lappend matrix $r
 }