Paris của các nhà toán học và vật lý học

⟦trang 24⟧

CÁC BÀI TOÁN

1. Giả sử mỗi chàng trai làm bạn với không ít hơn $m$ cô gái, còn mỗi cô gái — không nhiều hơn $m$ chàng trai ($m$ — là một số tự nhiên tùy ý). Chứng minh rằng trong trường hợp này điều kiện của định lý về việc ghép đôi được thỏa mãn.

2. Các học sinh trong câu lạc bộ đã giải các bài toán. Hóa ra mỗi người giải được 4 bài toán và mỗi bài toán được bốn học sinh giải. Chứng minh rằng có thể tổ chức việc trình bày lời giải sao cho mỗi học sinh trình bày đúng một bài toán và tất cả các bài toán đều được trình bày (mỗi bài một lần).

3. Cho một mạng vận tải. Tập hợp các đỉnh chứa lối ra nhưng không chứa lối vào được gọi là một lát cắt của mạng. Khả năng thông qua của lát cắt $B$ được gọi là số $c(B)$, bằng số các cung đi vào $B$. Nếu ký hiệu dòng chảy qua $\phi$, thì $|\phi|$ sẽ ký hiệu độ lớn của dòng chảy. Chứng minh rằng đối với mọi dòng chảy $\phi$ và mọi lát cắt $B$ đều đúng bất đẳng thức: $|\phi| \leq c(B)$.

4. Lát cắt $B$ được gọi là tối thiểu nếu khả năng thông qua của nó $c(B)$ — là nhỏ nhất trong số các khả năng thông qua của tất cả các lát cắt. Dùng thuật toán Ford—Fulkerson, suy ra rằng khả năng thông qua của lát cắt tối thiểu bằng độ lớn của dòng chảy cực đại — max $|\phi| = \min c(B)$ (định lý Ford—Fulkerson).

5. Kiểm tra rằng nếu $\phi$ — là luồng cực đại, thì lát cắt thu được bằng cách hợp tất cả các đỉnh không được đánh dấu (các dấu được tạo ra xuất phát từ luồng $\phi$, bằng phương pháp Ford—Fulkerson), là cực tiểu.

6. Chứng minh rằng hợp và giao của bất kỳ hai lát cắt cực tiểu nào cũng lại là một lát cắt cực tiểu.

7. Chứng minh rằng lát cắt từ các đỉnh không được đánh dấu (đối với luồng cực đại) là hợp của tất cả các lát cắt cực tiểu. Từ đó suy ra rằng lát cắt này không phụ thuộc vào việc các luồng được tạo ra bằng lát cắt cực đại nào.

TÀI LIỆU THAM KHẢO

1. А. Kофман, Р. Фор, Nghiên cứu vận trù, «Mir», 1966.
2. К. Берже, Lý thuyết đồ thị và ứng dụng của nó, IL, 1962.
3. Л. Форд, Д. Фолкерсон, Luồng trong mạng, «Mir», 1966.
4. О. Оре, Lý thuyết đồ thị, «Nauka», 1968.
5. Д. Гэйл, Lý thuyết các mô hình kinh tế tuyến tính, IL, 1963.

PARIS CỦA CÁC NHÀ TOÁN HỌC VÀ VẬT LÝ HỌC

Ở Paris, nhiều tòa nhà gắn liền với ký ức về những nhà khoa học lỗi lạc của các thế kỷ trước. Bên cạnh Louvre, nơi từng là thành trì của các vị vua, ngay trước cuộc cách mạng năm 1789 đã trở thành nơi họp của các viện sĩ. Mặc dù sau này, dưới thời Napoléon I, Louvre trở thành bảo tàng, nhưng ngay cả khi đó trong đó vẫn có một số nhà khoa học được bố trí nơi ở. Còn lưu giữ bức thư của Legendre, trong đó nhà toán học này khẩn khoản xin được cho ở trong phần cũ của cung điện.

Ở Paris có những con đường mang tên các nhà toán học, nhà vật lý và nhà thiên văn học, trong đó không phải tất cả các nhà khoa học này đều là người Pháp. Những cái tên đó là: Legendre, Réaumur, Pascal, Pierre Curie, Marie Curie, Lambert, Buffon, Franklin, Carnot, Arago, Descartes, Leibniz…

Câu «Số $z$ là số lớn nhất trong hai số $x$ và $y$» có thể viết bằng công thức như sau:

$$z = \frac{1}{2} (|x - y| + x + y).$$

Còn viết câu «Số $u$ là số lớn nhất trong ba số $x, y$ và $z$» như thế nào?

Chứng minh rằng từ АБАБАБ chia hết cho 7 (А và Б — là các chữ số bất kỳ).

CÂU HỎI BÓNG ĐÁ

Như đã biết, các trận đấu tranh cúp bóng đá được tổ chức theo cái gọi là hệ thống Olympic: đội thua bị loại, nếu hòa thì đấu lại.

Năm đó không có trận đấu lại, và có 75 đội tham gia các trận đấu.

Đã diễn ra bao nhiêu trận đấu tranh cúp?