Rất nhiều điều không có gì

Kvant 1977, số 3 tr. 12-14 Thẻ 0RN6

Bản dịch tự động sơ bộ, chất lượng thấp: có thể còn lỗi và câu chữ chưa tự nhiên. Bản này sẽ được thay bằng bản dịch tốt hơn. Bản gốc →

Anh tưởng tôi đã ngủ quên
Và tôi sẽ chịu đựng mọi thứ trong giấc ngủ,
Hoặc nghĩ những gì tôi nghĩ
Điều anh ấy nghĩ là “Tôi đang mơ.”
S. Marshak. Đến từ Coventry Patmore

Chúng tôi thu hút sự chú ý của độc giả bài toán, điều này đòi hỏi nhiều logic phức tạp cho lời giải:

Nhà toán học R nói với các nhà toán học P và S: “Tôi nghĩ đến hai số tự nhiên. Mỗi số lớn hơn một và tổng của chúng nhỏ hơn cm. Bây giờ tôi sẽ nói với nhà toán học P, với độ tin cậy từ S, tích của những số này, và tôi sẽ nói với nhà toán học S, với độ tin cậy từ P, tổng của chúng.” Anh ta đã thực hiện lời hứa của mình và đề nghị đặt ra những con số đã định. Cuộc đối thoại sau đây sẽ diễn ra giữa P và S (ta biểu thị phát biểu của P bằng chữ l kèm chỉ số, phát biểu của S bằng chữ σ):

“Xin lỗi, tôi không thể nói con số dự kiến là bao nhiêu.” (π₁)

Tôi biết trước là bạn không thể làm được. (σ₁)
Nhưng tôi biết họ, em yêu. (π₂)
Và tôi cũng biết họ. (σ₂)
Bây giờ hãy cố gắng giải mã những con số bạn có trong đầu.

Có thực sự có thể đoán được chúng?

Thoạt nhìn bài toán có vẻ như không hòa tan được: làm sao

Bit là đơn vị đo lường thông tin kép (TSB, tái bản lần thứ 3, 2 tập).

Có thể đoán được những con số khi không nói gì về chúng?

Hãy thử nó với một ví dụ. Cho R hỏi 7 và 42. Sau đó anh ta cho P biết số 294, S - 49. Tiếp theo thì sao? P nói rằng anh không thể đoán được những con số mà anh nghĩ đến. Tất nhiên là anh ấy có thể - anh ấy chỉ biết công việc của họ. Tuy nhiên, mặc dù anh ấy cũng biết rằng chúng là tự nhiên, nhiều hơn một và tổng của chúng nhỏ hơn một trăm. Điều này mang lại điều gì?

Chúng ta hãy biểu thị các số dự kiến bằng k₀ và l₀, và để định nghĩa, k₀ ₀ l₀. Chúng ta cũng biểu thị tích k₀ · l₀ bằng p₀ và tổng k₀ + l₀ bằng s₀.

Vì vậy, P được thông báo rằng p₀ = 294. Khi đó k₀ có thể bằng 2, 3, 6, 7 và 14, và l₀ sẽ lần lượt bằng 147, 98, 49, 42 và 21. Hai giá trị đầu tiên cho k₀ không phù hợp với chúng ta - đối với chúng s₀ > 100. Tuy nhiên, vẫn còn ba khả năng nữa. Điều này có nghĩa là P thực sự không thể đoán được những con số dự định.

Hãy tiếp tục. S khẳng định rằng anh ta đã biết trước rằng P không thể đoán được k₀ và l₀. Làm thế nào S đi đến kết luận này? Chắc chắn anh ta đã cố gắng bằng mọi cách có thể để biểu diễn s₀ đã biết là tổng của hai số hạng có thể chấp nhận được:

49 = 2 + 47 = 3 + 46 = …
… = 24 + 25.

R có thể đã dự định bất kỳ cặp số nào trong số này. Anh ta nói với P một số tích i · (49 − i), và S khẳng định rằng không có tích nào trong số đó P có thể đoán được những con số mà anh ta đang nghĩ tới.

Và nếu với ai đó, tôi có cả hai số i, 49 − i là số nguyên tố? Ví dụ: nếu R hỏi 2 và 47 thì anh ta nói với P 94 và P có thể đoán các con số một cách hoàn hảo.

Do đó, nếu R cho 7 và 42 thì S nhận được s₀ = 49 sẽ không có quyền sản phẩm (σ₁). Điều này có nghĩa là R không thể nghĩ ra 7 và 42.

Vì vậy, vẫn có thể nói điều gì đó về những con số dự định.

Trước những thay đổi đầu tiên, hãy nghĩ về hướng chuyển động. Tuy nhiên, phương pháp đoán đã hiển thị: lấy tất cả các cặp số có thể có k₀, l₀, thỏa mãn

sự bất bình đẳng
$2 \leq k_0 \leq l_0 \leq 97,$
$4 \leq k_0 + l_0 \leq 99,$
(1)
(2)

và kiểm tra xem họ có “chịu đựng được” cuộc đối thoại $(\pi_1) - (\sigma_2)$ hay không.

Vì việc tìm kiếm là hữu hạn trong mọi trường hợp nên về nguyên tắc có thể thực hiện theo cách này. Tuy nhiên, giải bài toán theo cách này thật nhàm chán. Chúng tôi đang cố gắng giảm bớt tình trạng quá mức cần thiết.

Trước hết, trước tiên chúng ta không phải $k_0$ và $l_0$ , mà là tổng của chúng $s_0$ : đối với cặp $\langle k_0, l_0 \rangle$ các tùy chọn có thể lớn hơn hai nghìn và đối với $s_0$ - nhỏ hơn một trăm. Tuy nhiên, ngay cả trên con đường này, mọi cuộc tìm kiếm đều dài dòng và nhàm chán.

Về giả thuyết Holbach-Euler

Thông tin nào có thể được trích xuất từ $(\pi_1)$ và $(\sigma_1)$ ? Họ có ý nghĩa gì? $(\pi_1)$ rõ ràng có nghĩa là $p_0$ không phân hủy duy nhất thành tích của hai thừa số thỏa mãn bất đẳng thức (1), (2);

$(\sigma_1)$ có nghĩa là Đối với bất kỳ phân tách số $s_0$ thành tổng của hai số hạng thỏa mãn bất đẳng thức (1), tích của chúng có tính chất $(\pi_1')$ .

Câu lệnh $(\pi_1')$ cho phép chúng ta loại bỏ một số tích, $(\sigma_1')$ - một số tổng.

Từ $(\sigma_1')$ suy ra rằng $s_0$ không thể được biểu diễn dưới dạng tổng của hai số nguyên tố: nếu $s_0' = q_1 + q_2$ , trong đó $q_1, q_2$ là số nguyên tố, thì số $q_1 \cdot q_2$ phân giải duy nhất thành tích của hai thừa số thỏa mãn bất đẳng thức (1), (2) và do đó, không có tính chất $(\pi_1')$ .

Nhưng bất kỳ số chẵn nào thỏa mãn bất đẳng thức (2) đều có thể được biểu diễn dưới dạng tổng của hai số nguyên tố (điều này được chứng minh bằng cách kiểm tra tuần tự các số 4, 6, 8, …, 98).

Do đó, $s_0$ là số lẻ. Ngoài ra, $s_0 - 2$ là một hợp số: nếu không thì $s_0 = 2 + (s_0 - 2)$ sẽ được biểu diễn dưới dạng tổng của hai số nguyên tố.

đơn giản. Sau khi loại bỏ các số không thỏa mãn hai điều kiện này, còn lại 24 khả năng là $s_0$ .

Ở trên chúng ta đã lợi dụng thực tế là tất cả các số chẵn từ 4 đến 98 đều có thể được biểu diễn dưới dạng tổng của hai số nguyên tố.

Năm 1742, một thành viên của Viện Hàn lâm Khoa học St. Petersburg, Christan Holbach, trong một bức thư gửi Leonhard Euler, đã đề xuất rằng bất kỳ số lẻ nào lớn hơn gót chân đều có thể được biểu diễn dưới dạng tổng của hai số nguyên tố. Trong thư trả lời của mình, Euler đưa ra giả thuyết rằng mọi số chẵn lớn hơn hai đều có thể được biểu diễn dưới dạng tổng của hai số nguyên tố. (Rất dễ rút ra giả thuyết Holbach từ giả thuyết Euler - hãy làm đi!)

Trong gần hai trăm năm, các giả thuyết của Holbach và Euler dường như hoàn hảo để chứng minh, mặc dù cuộc tìm kiếm gián tiếp của nhà toán học Millet đã kiểm chứng chúng tới 9.000.000.

Năm 1930, nhà toán học nổi tiếng Liên Xô L. G. Shinirelman đã chứng minh sự tồn tại của một $k$ sao cho mọi số tự nhiên $n > 1$ có thể được biểu diễn dưới dạng tổng của nhiều nhất $k$ số nguyên tố. Con số của Shinirelm $k$ khá lớn. Hiện nay người ta đã chứng minh rằng định lý Shinirelm đúng với $k = 20$ .

Năm 1934, viện sĩ I.M. Vinogradov đã chứng minh sự tồn tại của $n_0$ sao cho bất kỳ số lẻ nào $n > n_0$ đều có thể biểu diễn dưới dạng tổng của ba số nguyên tố. Có vẻ như trong thời đại máy tính, có thể hướng dẫn máy kiểm tra các số “còn lại” (từ 7 đến $n_0$ ), nhưng “hằng số Vinogradov” $n_0$ quá lớn (theo ước tính mới nhất $n_0 > 2^{216}$ ) nên việc kiểm tra này vượt quá khả năng cải tiến của máy tính.

Chưa có thành công đáng kể nào đạt được trong việc chứng minh giả thuyết Euler.

Đi sâu hơn vào rừng

Hóa ra $s_0 < 55$ có thể bắt nguồn từ $(\sigma_1')$ . (3)

Thật vậy, giả sử rằng $s_0 \geq 55$ . Khi đó $s_0$ không có tính chất $(\sigma_1')$ : nó có thể phân tích thành tổng của hai số hạng thỏa mãn bất đẳng thức (1) sao cho điều kiện $(\pi_1')$ không được thỏa mãn cho tích của chúng. Sự phân hủy này là: $s_0 = (s_0 - 53) + 53$ . $s_0 \geq 55$ ngụ ý $s_0 - 53 \geq 2$ . Tích $(s_0 - 53) \cdot 53$ phân tích duy nhất thành hai thừa số, với ý nghĩa là nó ít hơn: vì 53 là số nguyên tố nên một trong các thừa số nhất thiết phải có dạng 53d; kể từ $53 \cdot 2 > 100$ , $d = 1$ . Nhưng theo điều kiện $s_0$ có tính chất $(\sigma_1')$ . Mâu thuẫn!

Sau (3) cho $s_0$ , đã còn lại 11 khả năng:
$11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53.$

Bây giờ chúng ta hãy cố gắng thiết lập một cách dễ dàng, số nào trong số (4) thỏa mãn các điều kiện ( $\sigma'_1$ ). Đặt $s$ là một số tùy ý trong các số (4). Vì $s$ là số lẻ nên mọi khai triển của nó thành tổng đều có dạng $s = 2a + m$ . Giả sử $s$ không có thuộc tính ( $\sigma'_1$ ). Sau đó anh ta sẽ tìm một $a$ sao cho tích $2a \cdot m$ “giải mã” một cách duy nhất.

$a$ này không thể bằng một, vì trong trường hợp này $s = 2 + m$ và sản phẩm $2m$ bị phân hủy kép thành sản phẩm. Thật vậy, vì $m = s - 2$ là tổng số lẻ, $m = pq$ , trong đó $p > 2$ và $q > 2$ . Cả hai bản mở rộng

$2m = 2 \cdot pq = 2p \cdot q$

phù hợp: $2 + pq = 2 + m = s < 100$ và $2p + q = 2 + pq - (p - 1)(q - 2) < 2 + pq < 100$ .

Vì vậy, $a \geq 2$ .

Nếu $a \neq m$ thì $s = 2a \cdot m$ và $s = 2m \cdot a$ là hai khai triển khác nhau. Vì $2a + m = s < 100$ và $s$ không có thuộc tính ( $\sigma'_1$ ) nên phải có $2m + a \geq 100$ . Vì $s = 2a + m \leq 53$ , chúng ta có $m \leq 53 - 2a$ , $2m + a \leq 106 - 3a$ . Từ $2m + a \geq 100$ và $2m + a \leq 106 - 3a$ theo sau $a \leq 2$ . Vì vậy, $a = 2$ . Từ $2m + a \geq 100$ và $m \leq 53 - 2a$ hiện chúng tôi thu được $m = 49$ . Vì vậy, trong trường hợp này $s = 53$ , và sự phân hủy “đáng ngờ” là $53 = 4 + 49$ .

Nếu $a = m$ thì $s = 3a$ chia hết cho 3. Trong (4) có hai số như vậy: 27 và 51. “Đáng ngờ” là khai triển $27 = 9 + 18$ và $51 = 17 + 34$ .

Số 51 thực sự không có tính chất ( $\sigma'_1$ ): $51 = 17 + 34$ , và tích 17·34 khi phân tích thành hai thừa số chỉ cho một tổng, nhỏ hơn cống. Vì vậy, nó có thể bị loại khỏi danh sách “ứng cử viên cho $s_0$ ”.

Các số 27 và 53 thỏa mãn điều kiện ( $\sigma'_1$ ): $9 \cdot 18 = 2 \cdot 81$ và $2 + 81 < 100; 4 \cdot 49 = 7 \cdot 28$ và $7 + 28 < 100$ .

Vì vậy, còn lại 10 ứng viên để nghiên cứu thêm: 11, 17, 23, 27, 29, 35, 37, 41, 47, 53, tất cả đều có tính chất ( $\sigma'_1$ ).

“Vậy thì tôi cũng biết họ”

Cuối cùng, chúng tôi sử dụng $(\pi_2)$ và $(\sigma_2)$ .

Chúng ta có thể sử dụng $(\pi_2)$ và $(\sigma_2)$ giống như cách chúng ta đã làm với $(\pi_1)$ và $(\sigma_1)$ . Chúng tôi sẽ cố gắng làm mà không có nó.

Từ $(\sigma_2)$ và (3) ta suy ra

$s_0 < 33.$

Giả sử điều ngược lại: $s_0 \geq 33$ . Sau đó, $S$ , khai triển $s_0$ theo mọi cách có thể thành tổng của hai số hạng, chúng ta sẽ có trong số các khai triển này $s_0 = (s_0 - 31) + 31 = (s_0 - 29) + 29$ .

Nếu $P$ được cho biết tích của $(s_0 - 31) \cdot 31$ , thì anh ta có thể báo cáo rằng 31 là số nguyên tố, hiểu rằng $(s_0 - 31) \cdot 31$ được phân tách duy nhất thành tích của hai thừa số có tổng thỏa mãn (3). Trong trường hợp này, $P$ sẽ đoán $k_0$ và $l_0$ .

$P$ có cơ hội tương tự nếu sản phẩm $(s_0 - 29) \cdot 29$ đã được báo cáo.

Điều này có nghĩa là trong trường hợp $s = 53$ , phân tách “đáng ngờ” là $53 = 4 + 49$ .

Nếu $a = m$ thì $s = 3a$ chia hết cho 3. Trong (4) có hai số như vậy: 27 và 51. “Đáng ngờ” là sự phân tách $27 = 9 + 18$ và $51 = 17 + 34$ .

Các số 27 và 53 thỏa mãn điều kiện ( $\sigma'_1$ ): $9 \cdot 18 = 2 \cdot 81$ và $2 + 81 < 100; 4 \cdot 49 = 7 \cdot 28$ và $7 + 28 < 100$ .

Vì vậy, còn lại 10 ứng viên để nghiên cứu thêm: 11, 17, 23, 27, 29, 35, 37, 41, 47, 53, tất cả đều có tính chất ( $\sigma'_1$ ).

Thế thì chúng ta cũng biết họ

29 cũng không phù hợp, vì, vì $29 = 4 + 25 = 16 + 13$ : nếu $P$ có $p_0 = 16 \cdot 13$ , anh ta sẽ đoán $k_0$ và $l_0$ , vì trong tổng $2^{4-t} + 2^t \cdot 13$ chỉ có một là số lẻ; nếu $P$ có $p_0 = 4 \cdot 25$ , anh ấy cũng sẽ đoán $k_0$ và $l_0$ : trong số các tổng tương ứng không có