Hai lần về cùng một điều

45

Chắc hẳn nhiều bạn đã từng chơi xổ số hoặc ít nhất đã nghe nói đến trò chơi này. Chúng tôi cung cấp cho bạn một số cái nhìn sâu sắc về nó. Như trong phiên bản thông thường, vật phẩm chính của chúng tôi là một chiếc túi có “thùng” trên đó viết các số từ 0 đến 99. Các quy tắc của trò chơi như sau. Bạn được phép viết bất kỳ số nào từ 0 đến 99, mỗi số không quá một lần. Sau đó, một “thùng” được lấy ra khỏi túi. Nếu bất kỳ số nào được viết cho bạn có chữ số đầu tiên (hoặc thứ hai) khớp với chữ số đầu tiên (thứ hai tương ứng) của số được rút ra thì số của bạn sẽ nhận được 250 điểm. Con số trùng với số được rút sẽ được 500 điểm. Ví dụ: nếu rút ra số 95 thì bản thân nó nhận được 500 điểm, số 45 và 91 mỗi số nhận được 250 điểm, còn số 59 và 04 không nhận được gì (các số có một chữ số - 0, 1, 2, … - được viết dưới dạng số có hai chữ số - 00, 01, 02, …).

Để hiểu rõ hơn về luật chơi, chúng ta hãy chơi. Bạn có một mảnh giấy và một cây bút, tôi có một cái túi có “thùng”. Ví dụ, một vài con số về thực phẩm. Tôi lấy ra 66. Bạn ghi được bao nhiêu điểm? Cần tuyển bao nhiêu người mẫu? Rõ ràng là không quá 750. Và số lượng số tối đa bạn cần viết để chắc chắn gõ được số đó khi viết là bao nhiêu?

Hãy dành thời gian của bạn, suy nghĩ. Bạn đã nhận được bao nhiêu? 10? Phải. Ví dụ: bạn có thể viết các số 00, 01, 02, 03, …, 09 và sau đó, bất kể số nào được lấy ra khỏi túi, chữ số thứ hai của nó trùng với chữ số thứ hai của một trong các số của bạn, nghĩa là bạn sẽ nhận được ít nhất 250 điểm. Và số lượng ít hơn là không đủ. Rốt cuộc, nếu bạn viết ít hơn mười số, bạn sẽ tìm thấy số a không phải là trung bình của các chữ số trong các số của bạn và số b sẽ không phải là trung bình của các chữ số trong các số của bạn. Và sau đó nếu một “thùng” có số ab ​​được lấy ra khỏi túi, bạn sẽ không giành được gì cả.

Bài toán 1. Rút ra từ túi số nào nếu bộ 07, 29, 45, 68, 84, 71, 32, 16, 53 không nhận được gì?

Bây giờ câu hỏi khó hơn.

Cần viết tối đa bao nhiêu số để chắc chắn gõ được số đó khi viết?

Chúng ta hãy tạm dừng xổ số một phút và nhớ lại bàn cờ và quân xe, tất cả đều là các ô vuông nằm trên cùng một chiều ngang hoặc dọc với sân mà nó đứng. Hãy cho tôi biết, trên bàn cờ có thể coi tối đa bao nhiêu quân xe mà chúng không khác nhau?

46

Bất cứ ai ít nhất một chút quen thuộc với cờ vua sẽ trả lời ngay: tất nhiên là số tám, chẳng hạn như trong Hình 1.

Sau đó, một câu hỏi nữa: đặt trên bàn cờ 8 quân xe không loại trừ lẫn nhau. Ô vuông nào trên bàn cờ được đánh bao nhiêu lần?

Nếu các quân xe không cách xa nhau thì chúng nằm trên các hàng dọc khác nhau và các hàng ngang khác nhau, rồi trên mỗi hàng dọc và mỗi hàng ngang có một xe. Do đó, bất kỳ ô nào không có quân Xe chiếm giữ sẽ được chiến đấu với hai quân Xe (một theo chiều dọc, một theo chiều ngang).

Xổ số và cờ vua có điểm gì chung? Nhưng nhìn này. Hãy viết tất cả các số từ 00 đến 99 vào bảng vuông 10x10:

| 00 | 01 | 02 | 09 |
| :— | :— | :— | :— |
| 10 | 11 | 12 | 19 |
| :— | :— | :— | :— |
| 90 | 91 | 92 | 99 |

Chúng ta sẽ nói rằng số $ab$ sẽ là số $cd$ nếu $ab$ được điểm khi $cd$ được lấy ra khỏi túi, tức là nếu $a=c$ hoặc $b=d$. Hãy nhìn vào bảng của chúng tôi. Mỗi cái có những con số đứng cạnh nó trên cùng một đường ngang hoặc dọc. Chúng ta đã biết rằng nếu 10 số khác nhau (ví dụ: 00, 11, 22, …, 99) thì bất kỳ số nào từ 0 đến 99 sẽ trùng với một trong 10 số đó hoặc là hai số được chọn. trong obonkh

Hình 1.

trường hợp bộ của chúng tôi nhận được 500 điểm. Và bạn không thể ghi ít hơn mười con số và 250 điểm. Vậy là chúng ta đã trả lời được câu hỏi về xổ số. Chỉ còn lại một điều mơ hồ.

Bài toán 2. Có nhất thiết 10 số phải khác nhau thì tập hợp như vậy luôn cho kết quả 500 điểm không?

Câu hỏi này rất quan trọng. Vì vậy, trước khi đọc thêm, hãy kiểm tra đáp số của bạn trên trang. 60.

Và bây giờ chúng ta có thể giải câu bài toán phức tạp hơn - tìm xem có tổng cộng bao nhiêu trong một bộ 10 số có thể được 500 điểm.

Chúng ta đã biết rằng một bộ 10 số có một số ô vuông nhất định và mỗi ô vuông có một số điểm nhất định. Chúng ta có thể sử dụng một thuật toán đơn giản để tìm số ô vuông trong bảng đã cho.

Chúng ta đã biết rằng một bộ 10 số có một số ô vuông nhất định và mỗi ô vuông có một số điểm nhất định. Chúng ta có thể sử dụng một thuật toán đơn giản để tìm số ô vuông trong bảng đã cho.

bài toán này được các nhà toán học biết đến nhiều và thậm chí còn có tên riêng: nó được gọi là bài toán hoán vị. Đối với lời giải của nó, hãy lưu ý rằng bất kỳ chữ số nào trong số 10 chữ số khác nhau đều có thể được gán cho chữ số 0. Bạn có thể gán số cho cặp 0 và 1 như thế này: trước tiên, chúng ta gán bất kỳ chữ số nào trong số 10 chữ số cho cặp 0 và 1. Do đó, chúng ta nhận được 10 9 = 90 cặp số, bắt đầu bằng 0 và 1, v.v. Đáp số cho câu hỏi bài toán là 10! (đọc “10 giai thừa”).

Bài toán 3 (kiểm soát). Có bao nhiêu cách xếp 8 quân xe giống hệt nhau lên bàn cờ sao cho chúng không cạnh nhau?

Bây giờ chúng ta giả sử rằng chúng ta muốn đặt các quân xe không thuộc về nhau trên một bàn cờ xoay. Chúng ta sẽ thấy bao nhiêu đánh giá trong trường hợp này?

47

Hình 2.

Bí quyết của bài toán này là khi đế quay, chúng ta không thể phân biệt cách sắp xếp này với cách sắp xếp đối xứng tâm với nó.

Bài toán 4 (có thể điều khiển được và có nút vặn). Chúng ta có thể phân biệt trên một bàn cờ đang quay những cách sắp xếp mà trên một bàn cờ cố định có được với nhau bằng cách xoay 90° so với tâm của bàn cờ không?

Chúng ta hãy biểu thị số cách sắp xếp đối xứng tâm bằng $S$. Khi đó, tổng số vị trí của quân xe trên bàn quay có thể được biểu thị bằng công thức $S + \frac{8! - S}{2} = \frac{S + 8!}{2}$ và tất cả những gì chúng ta phải làm là tìm $S$.

Như thường lệ, chúng ta có 8 cách để xếp quân Xe lên hàng đầu. Nhưng nếu chúng ta đặt một quân xe ở hạng trên thì chúng ta sẽ phải đặt một quân xe đối xứng với nó ở hạng thấp hơn. Sau đó, đối với quân ở hạng thứ hai từ trên xuống chỉ có 6 khả năng, ở hàng thứ ba - 4, ở hàng thứ tư - 2, sau đó sự sắp xếp được xác định. Do đó, có $8 \cdot 6 \cdot 4 \cdot 2 = 2^4 \cdot 4!$ cách sắp xếp đối xứng và tổng số cách sắp xếp là $\frac{8! + 2^4 \cdot 4!}{2}$.

Bài toán 5 (kiểm soát). Có thể nhìn thấy bao nhiêu hàng quân xe đang nhớ về quá khứ của nhau trên một bến quay không sơn?

Bây giờ chúng ta hãy viết tất cả các số từ 1 đến 64 thành một hàng trên bàn cờ của chúng ta (ở hàng ngang trên cùng, từ trái sang phải, các số từ 1 đến 8, ở hàng tiếp theo, từ 9 đến 16, v.v.). Tổng của các số được viết trên các ô vuông nơi quân xe đứng (“tổng quân xe”) có thể có những giá trị nào?

Ở đầu bài viết này, bàn cờ đã giúp chúng ta giải bài toán về lado. Bây giờ thì ngược lại: Lodo sẽ giúp bạn giải quyết khó khăn bài toán trên bến tàu. Hãy để mỗi người chơi nhận được một số điểm nhất định trước khi bắt đầu trò chơi xổ số và để có cơ hội viết một số nhất định, họ phải cho số điểm bằng số này.

Bài toán 6 (kiểm soát). Cái nào trong số 10! Không có bộ số nào có lợi hơn nhau và số điểm yêu cầu là bao nhiêu?

Bằng cách giải bài toán này, bạn sẽ thực sự tính được “tổng xe” trên thanh $10 \times 10$, trong đó ký hiệu thập phân của các số sẽ thuận tiện.

Trên bến $8 \times 8$, mục nhập liên quan đến số 8 sẽ có lợi hơn. Cụ thể, bến tàu có các số có thể được biểu diễn dưới dạng “tổng” của hai bảng (Hình 2) và trên mỗi “triệu tập” tổng quân xe không phụ thuộc vào sự sắp xếp của các quân xe và bằng

$$0 + 8 + 16 + \dots + 56 = 224$$

trong học kỳ đầu tiên và

$$1 + 2 + 3 + \dots + 8 = 36$$

vào nhiệm kỳ thứ hai. Điều này có nghĩa là trong bất kỳ sự sắp xếp nào, hãy nhớ quân xe của nhau, tổng quân xe là 260.

Hãy quay lại với xổ số.

Bài toán 7. Bạn đã đủ điểm để viết tất cả các số từ 00 đến 99. Một thùng được lấy ra khỏi túi. Số điểm sẽ tăng (so với ban đầu) hay giảm đi?

Bài toán 8. Cho một bộ gồm 10 số khác nhau. Có phải luôn luôn có thể chia 90 số còn lại thành 9 bộ 10 số khác nhau?

Và cuối cùng, hai bài toán trên đế. Chúng ta sẽ nói rằng các số từ 1 đến 64 được viết trên bàn cờ theo “cách chính xác” nếu đối với tất cả các đội hình quân xe thì “tổng quân xe” đều giống nhau.

Bài toán 9. Chứng minh rằng có ít nhất $2 \cdot (8!)^2$ cách viết các số từ 1 đến 64 “một cách chính xác”.

Bài toán 10. “Tổng quân” ​​có thể nhận những giá trị nào nếu các số từ 1 đến 64 được viết “đúng cách”?