Contexte: le nombre de Ramsey donne le nombre minimum de sommets v dans le graphique complet K v de telle sorte qu'une coloration de bord rouge / bleu de K v ait au moins un rouge K r ou un bleu K s . Les limites pour des r , s plus grands sont très difficiles à établir.$R(r,s)$$v$$K_v$$K_v$$K_r$$K_s$$r, s$

Votre tâche consiste à sortir le nombre pour 1 ≤ r , s ≤ 5 .$R(r,s)$$1 \le r,s \le 5$

Contribution

Deux entiers avec 1 ≤ r ≤ 5 et 1 ≤ s ≤ 5 .$r, s$$1 \le r \le 5$$1 \le s \le 5$

Production

comme indiqué dans ce tableau:$R(r,s)$

  s   1    2    3    4      5
r +--------------------------
1 |   1    1    1    1      1
2 |   1    2    3    4      5
3 |   1    3    6    9     14
4 |   1    4    9   18     25
5 |   1    5   14   25  43-48

Notez que et s sont interchangeables: R ( r , s ) = R ( s , r ) .$r$$s$$R(r,s) = R(s,r)$

Pour vous pouvez sortir n'importe quel entier entre 43 et 48 inclus. Au moment de la publication de cette question, ce sont les limites les plus connues.$R(5,5)$$43$$48$

JavaScript (ES6), 51 49 octets

Prend des entrées dans la syntaxe de curry (r)(s).

r=>s=>--r*--s+[9,1,,13,2,,3,27,6][r<2|s<2||r*s%9]

Essayez-le en ligne!

Comment?

En première approximation, nous utilisons la formule:

 0  0  0  0  0
 0  1  2  3  4
 0  2  4  6  8
 0  3  6  9 12
 0  4  8 12 16

Si nous avons , nous ajoutons simplement 1 :$\min(r,s)<3$$1$

 1  1  1  1  1
 1  2  3  4  5
 1  3  -  -  -
 1  4  -  -  -
 1  5  -  -  -

Sinon, nous ajoutons une valeur choisie dans une table de recherche dont la clé est définie par:$k$

 k:                    table[k]:           (r-1)(s-1):         output:
 -  -  -  -  -         -  -  -  -  -       -  -  -  -  -       -  -  -  -  -
 -  -  -  -  -         -  -  -  -  -       -  -  -  -  -       -  -  -  -  -
 -  -  4  6  8   -->   -  -  2  3  6   +   -  -  4  6  8   =   -  -  6  9 14
 -  -  6  0  3         -  -  3  9 13       -  -  6  9 12       -  -  9 18 25
 -  -  8  3  7         -  -  6 13 27       -  -  8 12 16       -  - 14 25 43

JavaScript (Node.js) , 56 55 octets

f=(x,y)=>x<2|y<2||f(x,y-1)+f(x-1,y)-(x*y==12)-7*(x+y>8)

Essayez-le en ligne! J'ai remarqué que le tableau ressemble au triangle de Pascal mais avec des facteurs de correction. Edit: 1 octet enregistré grâce à @sundar.

Gelée ,  17  16 octets

’ScḢƊ_:¥9“ ı?0‘y

Essayez-le en ligne! Ou consultez une suite de tests .

0+,-./$R(5,5)$$43$$44$$45$$46$$47$$48$

Comment?

$R(r,s)\leq R(r-1,s)+R(r,s-1)$

This is ’ScḢƊ and would produce:

 1  1  1  1  1
 1  2  3  4  5
 1  3  6 10 15
 1  4 10 20 35
 1  5 15 35 70

If we subtract one for each time nine goes into the result we align three more with our goal (this is achieved with _:¥9):

 1  1  1  1  1
 1  2  3  4  5
 1  3  6  9 14
 1  4  9 18 32
 1  5 14 32 63

The remaining two incorrect values, $32$ and $63$ may then be translated using Jelly's y atom and code-page indices with “ ı?0‘y.

’ScḢƊ_:¥9“ ı?0‘y - Link: list of integers [r, s]
’                - decrement              [r-1, s-1]
    Ɗ            - last 3 links as a monad i.e. f([r-1, s-1]):
 S               -   sum                  r-1+s-1 = r+s-2
   Ḣ             -   head                 r-1
  c              -   binomial             r+s-2 choose r-1
        9        - literal nine
       ¥         - last 2 links as a dyad i.e. f(r+s-2 choose r-1, 9):
      :          -   integer division     (r+s-2 choose r-1)//9
     _           -   subtract             (r+s-2 choose r-1)-((r+s-2 choose r-1)//9)
         “ ı?0‘  - code-page index list   [32,25,63,48]
               y - translate              change 32->25 and 63->48

Python 2, 62 bytes

def f(c):M=max(c);u=M<5;print[48,25-u*7,3*M+~u-u,M,1][-min(c)]

Try it online!

Python 2, 63 bytes

def f(c):M=max(c);print[48,M%2*7+18,3*~-M+2*(M>4),M,1][-min(c)]

Try it online!

This is ridiculous, I will soon regret having posted this... But eh, ¯\_(ツ)_/¯. Shaved off 1 byte thanks to our kind Jonathan Allan :). Will probably be outgolfed by about 20 bytes shortly though...

Julia 0.6, 71 61 59 57 bytes

A->((r,s)=sort(A);r<3?s^~-r:3r+(s^2-4s+3)*((r==s)+r-2)-3)

Try it online!

Ungolfed (well, a bit more readable):

function f_(A)
  (r, s) = sort(A)

  if r < 3
    result = s^(r-1)
  else
    result = 3*r + 
               (s^2 - 4*s + 3) * ((r == s) + r - 2) -
               3
  end

  return result
end

What does it do?

Takes input as array A containing r and s. Unpacks the array into r and s with the smaller number as r, using (r,s)=sort(A).

If r is 1, output should be 1. If r is 2, output should be whatever s is.
$s^{r - 1}$ will be $s^0 = 1$ for r=1, and $s^1 = s$ for r = 2.
So, r<3?s^(r-1) or shorter, r<3?s^~-r

For the others, I started with noticing that the output is:

• for r = 3, $2\times3 + [0, 3, 8]$ (for s = 3, 4, 5 respectively).
• for r = 4, $2\times4 + \ \ [10, 17]$ (for s = 4, 5 respectively)
• for r = 5, $2\times5 + \ \ \ \ \ [35]$ (for s = 5)

(I initially worked with f(5,5)=45 for convenience.)

This looked like a potentially usable pattern - they all have 2r in common, 17 is 8*2+1, 35 is 17*2+1, 10 is 3*3+1. I started with extracting the base value from [0, 3, 8], as [0 3 8][s-2] (this later became the shorter (s^2-4s+3)).

Attempting to get correct values for r = 3, 4, and 5 with this went through many stages, including

2r+[0 3 8][s-2]*(r>3?3-s+r:1)+(r-3)^3+(r>4?1:0)

and

2r+(v=[0 3 8][s-2])+(r-3)*(v+1)+(r==s)v

Expanding the latter and simplifying it led to the posted code.

x86, 49 37 bytes

Not very optimized, just exploiting the properties of the first three rows of the table. While I was writing this I realized the code is basically a jump table so a jump table could save many bytes. Input in eax and ebx, output in eax.

-12 by combining cases of r >= 3 into a lookup table (originally just r >= 4) and using Peter Cordes's suggestion of cmp/jae/jne with the flags still set so that r1,r2,r3 are distinguished by only one cmp! Also indexing into the table smartly using a constant offset.

start:
        cmp     %ebx, %eax
        jbe     r1
        xchg    %eax, %ebx              # ensure r <= s

r1:
        cmp     $2, %al             
        jae     r2                      # if r == 1: ret r
        ret

r2:     
        jne     r3                      # if r == 2: ret s 
        mov     %ebx, %eax
        ret

r3:
        mov     table-6(%ebx,%eax),%al  # use r+s-6 as index
        sub     %al, %bl                # temp = s - table_val
        cmp     $-10, %bl               # equal if s == 4, table_val == 14
        jne     exit
        add     $4, %al                 # ret 18 instead of 14 

exit:
        ret                        

table:
        .byte   6, 9, 14, 25, 43

Hexdump

00000507  39 d8 76 01 93 3c 02 73  01 c3 75 03 89 d8 c3 8a  |9.v..<.s..u.....|
00000517  84 03 21 05 00 00 28 c3  80 fb f6 75 02 04 04 c3  |..!...(....u....|
00000527  06 09 0e 19 2b                                    |....+|

Python 2, 70 bytes

f=lambda R,S:R<=S and[1,S,[6,9,14][S-3],[18,25][S&1],45][R-1]or f(S,R)

Try it online!

MATL, 25 21 bytes

+2-lGqXnt8/k-t20/k6*-

Try it on MATL Online

Attempt to port Jonathan Allan's Jelly answer to MATL.

+2-lGqXn - same as that answer: compute $\binom{r+s-2}{r-1}$

t8/k - duplicate that, divide by 8 and floor

- - subtract that from previous result (We subtract how many times 8 goes in the number, instead of 9 in the Jelly answer. The result is the same for all but the 35 and 70, which here give 31 and 62.)

t20/k - duplicate that result too, divide that by 20 and floor (gives 0 for already correct results, 1 for 31, 3 for 62)

6* - multiply that by 6

- - subtract that from the result (31 - 6 = 25, 62 - 18 = 44)

Older:

+t2-lGqXntb9<Q3w^/k-t20>+

Try it on MATL Online

Python 3, 74 bytes

lambda *a:[[1]*5,[2,3,4,5],[6,9,14],[18,25],[43]][min(a)-1][max(a)-min(a)]

Try it online!

Proton, 52 bytes

Near-port of my Python answer.

c=>[48,(M=max(c))%2*7+18,3*M-(M>4?1:3),M,1][-min(c)]

Try it online!

Java 8, 62 bytes

(r,s)->--r*--s+new int[]{9,1,0,13,2,0,3,27,6}[r<2|s<2?1:r*s%9]

Lambda function, port of Arnauld's JavaScript answer. Try it online here.

Java, 83 bytes

int f(int x,int y){return x<2|y<2?1:f(x,y-1)+f(x-1,y)-(x*y==12?1:0)-7*(x+y>8?1:0);}

Recursive function, port of Neil's JavaScript answer. Try it online here.

C (gcc), 57 bytes

f(x,y){x=x<2|y<2?:f(x,y-1)+f(x-1,y)-(x*y==12)-7*(x+y>8);}

Recursive function, port of Neil's JavaScript answer. Try it online here.

C (gcc), 63 bytes

f(r,s){r=--r*--s+(int[]){9,1,0,13,2,0,3,27,6}[r<2|s<2?:r*s%9];}

Port of Arnauld's JavaScript answer. Try it online here.