$A=\left\{ 1;2;3;4;5;...;18;19;20 \right\}$ .
Trong tập hợp A có 10 sô chẵn nên để $a+b$ là số nguyên tố thì $a$ và $b$ không thể cùng chẵn
$\Rightarrow $ $k\ge 11$ .
Vì ta có thể chia 20 số trong S thành 10 cặp số sao cho tổng mỗi cặp là một số nguyên tố.
(1,4) ; (2,3) ; (5,8) ; (6,11) ; (7,10) ; (9,16) ; (12,13) ; (14,15) ; (17,20) ; (18,19)
$\Rightarrow $ Với $k=11$, ta luôn có hai số nằm trong cùng một cặp
Vậy $k=11$ thoả mãn yêu cầu đề bài.