Từ trường học bài toán đến vấn đề

2

A. Savin

NHIỆM VỤ TỪ TRƯỜNG

• ĐẾN VẤN ĐỀ

Sự sắp xếp và chuyển vị

Một ngày nọ, khi lật qua cuốn sách giáo khoa “Toán-5” của con trai tôi, tôi tình cờ thấy bài toán * sau đây.

Các tập của “Bách khoa toàn thư dành cho trẻ em” theo thứ tự sau: 1, 2, 6, 10, 3, 8, 4, 7, 9, 5. Làm thế nào để sắp xếp chúng theo thứ tự nếu bạn có thể lấy hai tập liền kề và đặt chúng cạnh nhau ở một vị trí mới (ở đầu, cuối hoặc giữa hai tập) mà không thay đổi thứ tự?

Khá nhanh chóng, tôi đã tìm được lời giải. Nó được mô tả trong Hình 1. Nhưng từ lâu, tôi đã phát triển thói quen phân tích giải pháp bài toán, và câu hỏi ngay lập tức nảy sinh: “Nếu nó không là gì khác thì sao?” Một phương pháp sắp xếp lại không phụ thuộc vào cách sắp xếp đầu tiên của các tập sách ngay lập tức xuất hiện trong đầu tôi. Đầu tiên, lấy tập 1 và tập ở bên phải đặt ở đầu, sau đó là tập thứ 2 và tập ở bên phải và đặt sau tập 1, v.v. Nếu tập mong muốn nằm ở cuối hàng thì trước tiên bạn nên lấy bất kỳ cặp tập nào chưa được cài đặt và sắp xếp lại chúng ở cuối hàng, sau đó có thể sắp xếp lại tập mong muốn.

Tôi đã thử phương pháp này theo cách sắp xếp được đề xuất trong bài tập và với bốn hoán vị, tôi đã sắp xếp các tập theo thứ tự mong muốn. Sau đó, tôi thực hiện cách sắp xếp: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. Sau sáu hoán vị (xem Hình 2), tôi đi đến cách sắp xếp sau: 1, 2, 3, 4, 5, 6, 7, 8, 10, 9. Sau đó, tôi phát hiện ra rằng phương pháp tầm xa không hiệu quả. Ngoại trừ quyển thứ 9 ra, chỉ còn lại một quyển thứ 10, cũng không có gì có thể dời đến cuối hàng.

Tôi sắp xếp lại các tập theo cách tương tự nhưng đặt các cặp khác ở cuối hàng. Việc sắp xếp lại mất nhiều thời gian hơn, nhưng kết quả vẫn như cũ - một lần nữa ở cuối hàng có sự kết hợp của 10, 9, điều mà phương pháp của tôi không thể giải quyết được. Và sau đó tôi nhớ rằng một tình huống tương tự sẽ xảy ra trong trò chơi ký hiệu “15” *). Ở đó, bằng cách di chuyển cơ thể, không thể di chuyển từ vị trí trong Hình 3 sang vị trí trong Hình 4.

Ý tưởng chứng minh thực tế này dựa trên thao tác “chuyển vị”. Sự chuyển vị của một dãy số nhất định được gọi là sự thay đổi của hai số bất kỳ trong số đó. Đồng thời, người ta chứng minh rằng nếu một dãy số được lấy từ một dãy số khác bằng cách sử dụng số chẵn chuyển vị thì không thể cộng kết quả tương tự bằng cách sử dụng số lẻ chuyển vị và ngược lại, nếu dãy số đó

*) Trong ấn bản mới nhất của sách giáo khoa “Toán học-5” (M., “Prosveshcheniye”, 1976), bài toán này xuất hiện dưới số 1249.

*) Xem «Kvant», 1974, số 2, tr. 26.

3

Vì số lượng các số có được từ số khác bằng số lẻ chuyển vị nên không thể có được số đó bằng số chẵn chuyển vị.

Vẫn còn phải tìm hiểu xem thao tác được mô tả trong nhiệm vụ có tương ứng với số chuyển vị chẵn hay lẻ hay không. Di chuyển một tập đến một vị trí mới tương đương với một loạt chuyển vị: đầu tiên là với tập gần nhất, sau đó với tập tiếp theo, v.v., cho đến khi nó đứng ở vị trí mới. Tương tự như vậy, việc di chuyển âm lượng tiếp theo tương đương với một loạt các chuyển vị có cùng âm lượng như trong trường hợp đầu tiên. Tổng số chuyển chuyển sẽ bằng hai lần số chuyển chuyển khi chuyển một tập nên thao tác của chúng ta tương đương với số chuyển chuyển chẵn.

Do đó, một số khoảng cách âm lượng của các thao tác được chỉ định trong công việc có thể được đặt hàng, nhưng một số khoảng cách khác thì không thể. Cụ thể, các khoảng cách 1, 2, 3, 4, 5, 6, 7, 8, 10, 9 được lấy từ các khoảng cách 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 bằng một số lẻ chuyển vị và do đó, khoảng cách của các phép toán không thể quy đổi thành khoảng cách đó.

Xin lưu ý rằng trong lý luận của chúng tôi, chúng tôi bỏ qua thực tế là có 10 tập. Với sự thành công tương tự, những lý luận này có thể được thực hiện cho bất kỳ số tập nào khác.

Nhưng việc chúng tôi sắp xếp lại hai tập cùng một lúc là rất có ý nghĩa. Thật vậy, nếu chúng ta sắp xếp lại từng tập một, thì với bất kỳ khoảng cách ban đầu nào với thao tác như vậy, chúng ta có thể sắp xếp các tập theo thứ tự. Điều gì sẽ xảy ra nếu bạn sắp xếp lại ba tập? Còn bốn thì sao?…

Một nửa số câu hỏi này có thể được trả lời ngay lập tức. Việc sắp xếp lại một số tập chẵn tương ứng với một số chuyển vị chẵn; do đó, với thao tác như vậy, không thể chuyển đổi cách sắp xếp này sang cách sắp xếp khác, do nó có số lượng chuyển vị lẻ.

4

Hy, nếu chúng ta sắp xếp lại ba tập thì sao? Hãy thử nó! Bắt đầu với bao nhiêu tập? Ba không đủ, hãy lấy bốn. Chúng ta hãy xem có thể thu được sự sắp xếp nào từ cách sắp xếp theo thứ tự: 1, 2, 3, 4 - từ đó 2, 3, 4, 1 và 4, 1, 2, 3, từ đó 3, 4, 1, 2… thế là xong! Những hoán vị như vậy được gọi là tuần hoàn vì chúng sắp xếp lại các số trong một vòng tròn - nếu một cách sắp xếp được viết dọc theo một vòng tròn, thì bất kỳ cách sắp xếp nào khác đều có thể được đọc bắt đầu từ một vị trí nhất định (Hình 5). Nhưng không có hai sự sắp xếp nào
1, 2, 3, 4
1, 2, 4, 3
1, 3, 2, 4
1, 3, 4, 2
1, 4, 2, 3
1, 4, 3, 2
không thể được dịch sang nhau bằng các hoán vị tuần hoàn, tuy nhiên mỗi trong số chúng tương ứng với ba cách sắp xếp nữa, thu được bằng các hoán vị tuần hoàn. Như vậy, tất cả 24 cách sắp xếp khác nhau của các số 1, 2, 3 và 4 (kiểm tra xem có 24 trong số đó không) được chia thành 6 nhóm gồm 4 cách sắp xếp trong một nhóm và với phép tính của chúng ta, chúng ta không thể thu được từ cách sắp xếp của một nhóm sự sắp xếp của một nhóm khác.

Liệu tình trạng này có được duy trì nếu chúng ta lấy không phải bốn mà là năm tập hoặc lớn hơn? Hóa ra là không! Trình tự sắp xếp sau đây đóng vai trò quyết định ở đây:
1, 2, 3, 4, 5 → 1, 3, 4, 5, 2 → 4, 5, 2, 1, 3 → 2, 1, 3, 4, 5.

Sắp xếp lại ba tập cùng một lúc, chúng tôi đổi chỗ tập thứ nhất và thứ hai, trả phần còn lại về vị trí cũ. Theo cách tương tự, chúng ta có thể sắp xếp lại hai tập liền kề bất kỳ, không chỉ khi chúng ta có năm tập mà còn đối với bất kỳ số lượng lớn tập nào. Thật vậy, nếu hai tập này không phải là tập cuối cùng thì lấy tập tiếp theo sau, chúng ta sắp xếp lại ba tập này về phía trước, sau đó thay thế hai tập đầu tiên (như hình) và lại

Chúng ta hãy trả ba tập về chỗ cũ. Kết quả là tất cả các tập sẽ được đặt ở vị trí ban đầu, ngoại trừ hai tập mà chúng tôi đã chọn sẽ được đặt vào các vị trí. Nếu chúng ta muốn đặt hai tập cuối vào đúng vị trí thì trước tiên chúng ta sẽ lấy ba tập đầu tiên, đặt chúng ở cuối, sau đó thực hiện quy trình đã mô tả và cuối cùng đặt các tập ở đầu vào vị trí cũ.

Telery, rõ ràng, tuyên bố sẽ không gây bất ngờ cho bạn: nếu số lượng tập không nhỏ hơn ly, thì bất kỳ sự sắp xếp nào của các tập này đều có thể được chuyển đổi thành một sự sắp xếp theo thứ tự, sắp xếp lại các momas thành bộ ba *). Rốt cuộc, nếu bạn di chuyển các tập lân cận đến các vị trí, trước tiên bạn có thể di chuyển tập đầu tiên đến vị trí đầu tiên, sau đó chuyển tập thứ hai sang vị trí thứ hai, v.v.

Điều gì sẽ xảy ra nếu năm tập được sắp xếp lại? Bảy tập mỗi tập? Nói chung là theo tập 2n+1? Lời giải Tôi chưa từng thấy vấn đề này ở đâu cả.

Bạn có thể hỏi: “Ai cần những thay đổi này?” Hóa ra là chúng cần thiết, và rất thường xuyên, chẳng hạn, lý thuyết về hoán vị đóng một vai trò quan trọng trong câu hỏi lời giải - liệu có thể có nghiệm của một phương trình đại số đã cho *). Vì vậy, chúng tôi đã giải được bài toán M404 («Kvant», 1976, số 9).

5

không phải bậc $n$ có thể được biểu thị bằng cách sử dụng căn thức (như được thực hiện đối với phương trình bậc hai). Người ta nhận thấy rằng các phương trình bậc ba và bậc bốn có tính chất này, và đối với các phương trình bậc năm trở lên, các nghiệm, theo quy luật, không còn có thể được biểu thị thông qua các hệ số sử dụng căn thức.

Điều này đã được thảo luận trong «Kvant», gần đây nhất là trong các bài báo “Nhóm” và “Đại số - Cổ đại và Hiện đại” («Kvant», 1976, Số 10). Nếu đọc chúng, bạn sẽ nhận thấy ngay rằng các biến thể tích mà chúng ta đang xem xét là các hoán vị tạo ra một nhóm (mặc dù không phải toàn bộ nhóm hoán vị $S_n$ - đây là vấn đề) và các hoán vị xung quanh vòng tròn gồm bốn phần tử tạo thành một nhóm tuần hoàn. có thể lý thuyết nhóm sẽ giúp bạn (mặc dù, rất có thể, bài toán này được giải quyết bằng các thông báo “tổ hợp”).

Bây giờ, chúc thành công cho những ai quyết định giải lời giải cuối cùng của bài toán, chúng tôi sẽ bổ sung thêm bài toán thú vị hơn vào sách giáo khoa.

Một hay nhiều?

Tìm các số tự nhiên nguyên sao cho tổng của ba số đó và 1 chia hết cho một số nguyên.

Điều đầu tiên bạn nghĩ đến là lấy tất cả các số bằng 1. Bộ bốn số thực như vậy thỏa mãn điều kiện bài toán. Không có lời giải nào khác sao? Tôi đã thấy cái này bài toán ở đâu đó. Tôi mở cuốn sách của I. L. Babinskaya “Bài toán tối ưu hóa toán học” (M., “Hayka”, 1975) và tìm thấy nó ở số 142. Tôi đang tìm đáp số. Tôi đọc - “Ví dụ: 1, 2, 3, 7.” đáp số này KHÔNG PHẢI LÀ CĂNG THẲNG đối với tôi. Đối với tôi, điều này giống như đáp số: “Ví dụ: 2” cho câu hỏi: “Các nghiệm của phương trình $x^2 - 5x + 6 = 0?$ là gì.”

Không… Tôi đã thấy bài toán tương tự ở nơi khác. Tất nhiên, “Bộ sưu tập bài toán về tối ưu hóa toán học Moscow” (M., “Prosveshchenie”, 1965), tr. 70, bài toán 215. Đây rồi.

215. Tên của bộ ba số $a, b, c$, khác 1 thì sao

tích của hai bộ ba bất kỳ cộng vào một sẽ được chia cho số nguyên tố.

B đáp số là tập duy nhất: 2, 3, 7.

Có đúng không, đáp số rất giống với đáp số giữa chúng ta bài toán, mặc dù ở đây chúng ta không nói về bốn mà là về ba con số. Điều gì xảy ra với hai số? Đối với những cặp số nào thì tổng của mỗi số đó chia hết cho số kia? Một bài toán về bốn số dành cho học sinh lớp 5, một bài toán dành cho học sinh lớp 7-10… Tuy nhiên, chúng ta hãy lấy hết can đảm và có mặt để giải quyết lời giải.

Nếu một trong hai số này là 1 thì số thứ hai phải là ước số của 2: 1 hoặc 2. Dễ dàng kiểm chứng rằng cả hai cặp (1, 1) và (1, 2) đều thỏa mãn điều kiện bài toán.

Giả sử không có số nào bằng 1. Khi đó, hiển nhiên những số này là nguyên tố cùng nhau. Đặt $a < b$, sau đó $a + 1 \leq b$, nhưng $a + 1$ chia hết cho $b$, do đó $a + 1 \geq b$. Theo sau đó là $a + 1 = b$. Và vì $b + 1$ chia hết cho $a$, nên $a + 2$ chia hết cho $a$, do đó 2 chia hết cho $a$, và vì $a \neq 1$, nên $a = 2$, $b = 3$.

Vì vậy, có tất cả ba cặp số sao cho tổng của một trong số chúng và một số chia hết cho số kia: (1, 1), (2, 1), (3, 2).

lời giải khá đơn giản của bài toán này khiến tôi nghĩ đến việc cố gắng giải quyết bài toán tổng quát cùng một lúc:

“Tìm $n$ các số sao cho tích của bất kỳ $n - 1$ nào trong số chúng cộng vào một thì chia hết cho số còn lại.”

Hãy chứng minh hai bổ đề.

Bổ đề 1. Giả sử các số $a_1, a_2, \dots, a_n$ có tính chất là tích của bất kỳ $(n - 1)$ nào trong số chúng có tổng với 1 thì chia hết cho số dư. Sau đó, cộng số $a_{n+1} = 1$ với chúng, chúng ta được một tập hợp các số, tích của bất kỳ $n$ nào trong tổng của 1 được chia cho số dư. Và ngược lại, nếu trong số $n + 1$ có 1 và tích của bất kỳ $n$ nào trong số chúng trong tổng 1 được chia cho số dư, thì bằng cách loại bỏ khỏi

6

Đây là một tập hợp gồm một, chúng ta có một tập hợp gồm n số, tích của bất kỳ n - 1 nào trong số đó, tổng bằng một, được chia cho phần còn lại.

Công thức của bổ đề thì phức tạp nhưng cách chứng minh thì tầm thường. Chỉ cần sử dụng thực tế là nhân một số với một không làm thay đổi số đó và thực tế là bất kỳ số nào cũng chia hết cho một.

Bổ đề thứ hai có ý nghĩa hơn.

Bổ đề 2. Giả sử các số $a_1, a_2, \dots, a_n$ có tính chất là tích của bất kỳ $(n-1)$ nào trong số chúng có tổng với 1 thì chia hết cho phần còn lại. Sau đó, cộng số $a_{n+1} = a_1 a_2 \dots a_n + 1$ với chúng, chúng ta sẽ có một tập hợp các số, tích của bất kỳ n nào trong số đó, tổng bằng đơn vị, được chia cho phần còn lại.

Để chứng minh điều đó, bạn cần kiểm tra hai câu.

Đầu tiên là tích của n số đầu tiên được cộng vào số 1 sẽ chia hết cho $a_{n+1}$ - theo định nghĩa của số $a_{n+1}$.

Thứ hai là dành cho trường hợp sản phẩm có kèm số $a_{n+1}$. Hãy biểu thị bằng $A_i$ tích của n - 1 số đầu tiên không có $a_i$: chúng ta phải chứng minh rằng $A_i a_{n+1} + 1$ chia hết cho $a_i$. Để làm điều này, chỉ cần lưu ý rằng $a_{n+1} = a_i A_i + 1$; rồi $A_i a_{n+1} + 1 = A_i (A_i a_i + 1) + 1 = a_i A_i^2 + (A_i + 1)$, và số hạng đầu tiên được chia cho $a_i$, số hạng thứ hai, nằm trong ngoặc, cũng chia hết cho mệnh đề của bổ đề.

Từ những bổ đề này, suy ra rằng trong bài toán với tremiya, các số sẽ như sau lời giải: $(1, 1, 1), (1, 1, 2), (1, 2, 3), (2, 3, 7)$; trong bài toán với bốn số $(1, 1, 1, 1), (1, 1, 1, 2), (1, 1, 2, 3), (1, 2, 3, 7), (2, 3, 7, 43)$. Vẫn còn phải tìm hiểu xem có lời giải nào khác không.

Rõ ràng, không có lời giải mới chứa các đơn vị cho $n=3$ (bằng cách loại bỏ một trong các đơn vị, theo Bổ đề 1, chúng ta sẽ thu được một lời giải bài toán mới với hai số, nhưng không có lời giải nào khác trong đó). Bây giờ hãy đặt $(x, y, z)$ là một số lời giải bài toán với ba số. Dễ dàng chứng minh được rằng hai số bất kỳ trong số này phải là số nguyên tố cùng nhau. Hãy để $2 \leq x < y < z$.

Hãy viết ra các thư từ:

$$\begin{align*} xy + 1 &= k_1 z, \\ xz + 1 &= k_2 y, \\ yz + 1 &= k_3 x. \end{align*}$$

Ở đây $k_1, k_2, k_3$ là các số tự nhiên. Thay đổi sự tương ứng này, chúng ta nhận được: $xyz(xyz + x + y + z) + xy + yz + xz + 1 = k_1 k_2 k_3 xyz$.

Theo đó, $xy + yz + xz + 1$ chia hết cho $xyz$, tức là

$$xy + yz + xz + 1 = Axyz,$$

trong đó $A$ là số tự nhiên. Chia cả hai vế của đẳng thức này cho $xyz$, chúng ta nhận được

$$\frac{1}{x} + \frac{1}{y} + \frac{1}{z} + \frac{1}{xyz} = A.$$

Giá trị nhỏ nhất của $A$ sẽ thu được ở các giá trị nhỏ nhất của $x, y, z$, tức là ở $x=2, y=3, z=4$ (thực tế là $z \geq 5$). Từ đây

$$A \leq \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{2 \cdot 3 \cdot 4} = \frac{27}{24},$$

và vì $A$ là số tự nhiên nên nó bằng 1. Vì vậy, chúng ta cần tìm tất cả các số tự nhiên $x, y$ và $z$ sao cho $2 \leq x < y < z$ và

$$\frac{1}{x} + \frac{1}{y} + \frac{1}{z} + \frac{1}{xyz} = 1.$$

Hãy để chúng tôi chứng minh điều đó $x=2$. Thật vậy, nếu $x \geq 3$ thì $y \geq 4, z \geq 5$, do đó,

$$1 = \frac{1}{x} + \frac{1}{y} + \frac{1}{z} + \frac{1}{xyz} \leq \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{3 \cdot 4 \cdot 5} = \frac{48}{60}.$$

Chúng tôi đã nhận được một sự mâu thuẫn. Vì vậy, $x=2$. Sau đó, thư từ được viết như thế này:

$$1 = \frac{1}{2} + \frac{1}{y} + \frac{1}{z} + \frac{1}{2yz}.$$

Biểu thị $y$ từ đây, chúng ta nhận được

$$y = 2 + \frac{5}{z - 2}.$$

Điều này có nghĩa là $z-2$ là ước số của số 5, tức là $z=3$ hoặc $z=7$. Trong trường hợp đầu tiên $y=7$, trong trường hợp thứ hai $y=3$.

Vì vậy, $(2, 3, 7)$ là lời giải bài toán duy nhất có ba số không chứa đơn vị, do đó, chúng tôi cũng đã viết ra tất cả lời giải của bài toán này.

Hãy xem liệu có lời giải bài toán nào khác có bốn số không.

7

Rõ ràng, ở đây chỉ cần xem xét những lời giải không chứa một là đủ. tức là các số tự nhiên $x, y, z, u$ sao cho $2 \leq x < y < z < u$ và
$$xyz + 1 = k_1u,$$
$$xyu + 1 = k_2z,$$
$$xzu + 1 = k_3y,$$
$$yzu + 1 = k_4x,$$
trong đó $k_1, k_2, k_3$ và $k_4$ là số tự nhiên. Thay đổi sự tương ứng này, chúng ta thu được, tương tự như trường hợp trước, rằng
$$xyz + uxy + xzu + yzu + 1 = Axyzu,$$
trong đó $A$ là số tự nhiên hoặc
$$\frac{1}{x} + \frac{1}{y} + \frac{1}{z} + \frac{1}{u} + \frac{1}{xyzu} = A.$$
Vì $x \geq 2, y \geq 3, z \geq 4, u \geq 5$ thì
$$A \leq \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{2 \cdot 3 \cdot 4 \cdot 5} = \frac{31}{24},$$
do đó $A = 1$. Hơn nữa, nó được thể hiện theo cách tương tự như $x=2, y=3$. Hiện nay
$$\frac{1}{z} + \frac{1}{u} + \frac{1}{6zu} = \frac{1}{6},$$
Ở đâu
$$z = 6 + \frac{37}{u - 6}.$$
Điều này có nghĩa là $u-6$ là ước số của 37, tức là $u=7, z=43$ hoặc $u=43, z=7$. Vì vậy, một lần nữa chúng tôi chỉ nhận được lời giải hiện có. Điều này có nghĩa là trong trường hợp này tất cả lời giải đều được liệt kê.

Kết quả thu được minh họa cho giả thuyết của chúng tôi rằng hơn nữa tất cả lời giải bài toán cho các số $n$ sẽ được lấy từ lời giải bài toán cho các số $n-1$ sử dụng Bổ đề 1 và 2. Than ôi! Giả thuyết này không chính xác, ít nhất là với $n-5$ - ngoài lời giải (2, 3, 7, 43, 1807), thu được bằng Bổ đề 2, còn có một giả thuyết nữa: (2, 3, 7, 47, 395).

Điều gì sẽ xảy ra tiếp theo? Liệu lời giải bài toán đối với một số lượng lớn các số có thu được bằng cách áp dụng Bổ đề 1 và 2 cho hai nghiệm hiện không chứa một hay một hoặc thậm chí hai nghiệm nữa sẽ xuất hiện? Cho đến nay đây là một vấn đề.

Có bao nhiêu phân chia?

bài toán “sự khéo léo” sau đây cũng xuất hiện trong nhiều cuốn sách dành cho học sinh.

Hình 6.

Chiều dài của thước không có vạch chia là 13 cm. Cách đặt 4 vạch chia bên trong thước để với sự trợ giúp của nó, bạn có thể đặt bất kỳ độ dài nào đã cho sang một bên. Ở đây bạn cũng cần chỉ ra độ dài tương ứng trực tiếp trên thước, từ vạch chia này đến vạch chia khác (hoặc đến hết thước).

Hình 6 hiển thị một trong lời giải của bài toán này. Việc cố gắng tìm hiểu xem có lời giải nào khác là điều tự nhiên hay không, nhưng những câu hỏi thú vị hơn nhiều cũng là: tại sao chính xác lại có bốn cách chia? Nếu có ba thì sao? Thước dài nhất mà bạn có thể đánh dấu 4 vạch chia với thuộc tính đã chỉ định là thước nào? Và nói chung, số vạch chia nhỏ nhất cần đặt trên thước có chiều dài $n$ (cm) để có thể vẽ được tất cả các đoạn nguyên từ 1 cm đến $n$ (cm) là bao nhiêu?

Như mọi khi, chúng tôi bắt đầu với các mẫu. Đối với một cây thước dài 1 cm thì không cần chia vạch. Với chiều dài 2cm và

8

Hình 7.

3 cm là đủ cho một lần chia. Với chiều dài 4, 5, 6 cm, hai vạch chia là đủ, nhưng một vạch là chưa đủ; có chiều dài 7, 8, 9 cm thì cần ba vạch chia (hai vạch là không đủ), với chiều dài 10, 11, 12, 13 cm - bốn vạch chia (ba vạch là không đủ). Những kết quả này có được bằng cách tìm kiếm thông qua các tùy chọn; sự sắp xếp tương ứng được thể hiện trong Hình 7, nhưng khi chiều dài của dòng tăng lên, việc thực hiện tìm kiếm hoàn chỉnh ngày càng trở nên khó khăn hơn. Chúng ta cần một số phương pháp chung. Trước tiên chúng ta hãy thử ước tính số lượng các phần (trên và dưới).

Cho thước chia có $k$ trên thước có chiều dài $n$ (cm). Có bao nhiêu đoạn thẳng khác nhau (không phải các đoạn có độ dài khác nhau mà chỉ đơn giản là các đoạn khác nhau) có các đầu ở điểm chia hoặc ở đầu thước? Vì bất kỳ cặp điểm nào được liệt kê đều xác định một đoạn và có $k+2$ trong số chúng, nên sẽ có $(k+2)(k+1)/2$ đoạn. Và vì, theo điều kiện, bài toán phải có $n$ có độ dài khác nhau và một số đoạn dài có thể trùng nhau, nên bất đẳng thức phải được thỏa mãn

$$n \geq \frac{(k+2)(k+1)}{2}.$$

Theo đó, trên một đoạn có độ dài $n$ cần đặt ít nhất $(\sqrt{8n+1}-3)/2$ phép chia (nếu số này không phải là số nguyên thì phải ở gần nó hơn số nguyên).

Có lẽ chia bao nhiêu là đủ? Tất nhiên, $(n-1)$ là đủ (có thể áp dụng tất cả các cách chia centimet), nhưng liệu có thể đạt được với số lượng nhỏ hơn không?

Hãy thử sắp xếp các phần chia $k$ sau: đầu tiên chúng ta đặt các phần chia $m$ cho mỗi centimet, sau đó chia cho các phần $(m+1)$ (cm), một lần nữa đến $(m+1)$ (cm), v.v., cho đến khi chúng ta đặt tất cả các phần chia $k$. Bây giờ chúng ta hãy xem xét một thước kẻ có đầu bên phải $(m+1)$ (cm) tính từ phép chia cuối cùng. Độ dài của thước $l$ này có thể được biểu thị bằng $k$ và $m$: $l = m + (k-m)(m+1) + m+1 = -m^2 + m(k+1) + (k+1)$.

Sử dụng công thức chia có số dư $s = p(m+1) + q$, dễ dàng chứng minh được rằng với mọi $m$ thì cách sắp xếp phép chia cũng thỏa mãn điều kiện bài toán.

Chúng ta hãy lưu ý một tính chất quan trọng hơn của cách sắp xếp các phép chia này - nếu đoạn bên phải được rút ngắn bằng bất kỳ số nguyên centimet nào thì các điểm chia vẫn sẽ đáp ứng