perfectstrong

Tìm số xâu có độ dài $n$ xây dựng từ bảng chữ cái gồm $m$ ký tự sao cho bất kỳ $p$ ký tự liên tiếp nào trong xâu cũng đôi một phân biệt ($p \le m$).

Không biết bài này đã có ai đăng chưa ?

Ta sử dụng định nghĩa dãy Fibonacci như sau: $F_1 = 1; F_2 = 2; F_{n} = F_{n-1}+F_{n-2} \, \forall n \ge 3$.

Câu 1: Chứng minh rằng mọi số nguyên dương $N \ge 1$ luôn có thể phân tích tổng của một số hữu hạn số Fibonacci $F_n$ phân biệt.

Câu 2: Gọi $L^*(N)$ là độ dài của cách phân tích $N$ thành tổng các số Fibonacci phân biệt sao cho số số hạng là nhiều nhất. Một cậu học trò không biết làm sao để tìm $L^*(N)$, nên cậu đề xuất một thuật toán $H$ như sau:

1. Gọi $m_N$ là số nguyên dương nhỏ nhất sao cho $S_N = \sum\limits_{n=1}^{m_N} F_n \ge N$
2. Nếu $S_N=N$ thì $L^*(N) = m_N$, tức là $S_N$ là cách phân tích cần tìm.
3. Nếu $S_N > N$ thì đặt $d_N = S_N - N$
4. Phân tích $d_N$ thành tổng các số Fibonacci phân biệt sử dụng thuật toán $H'$
5. Loại bỏ những số Fibonacci nào trong $S_N$ nào xuất hiện trong $d_N$, thu được $S'_N$. Khi đó, $S'_N$ là kết quả của thuật toán.

Thuật toán $H'$: phân tích một số nguyên dương $N$ thành tổng các số Fibonacci phân biệt theo nguyên tắc tham lam giảm dần (decreasing greedy):

1. Gọi $i$ là chỉ số lớn nhất sao cho $F_i \le N$.
2. Đặt $N'=N-F_i$.
3. Nếu $N'=0$ thì dừng.
4. Nếu $N'>0$ thì thay $N$ bởi $N'$, và quay lại bước 1.

Các chỉ số $i$ tìm được sẽ cho ta cách phân tích $N$ thành ít số Fibonacci nhất có thể.

a. CMR thuật toán $H'$ sẽ tìm ra phân tích Fibonacci ngắn nhất có thể

b. CM tính đúng đắn của thuật toán $H$, tức là $H$ sẽ cho ra một phân tích Fibonacci, dù cho có thể không phải là phân tích tối ưu.

c. Ta muốn đánh giá hiệu suất của $H$. Gọi $L^H(N)$ là độ dài của cách phân tích bởi thuật toán $H$. Tìm $a,b$ tốt nhất sao cho \[\mathop {\lim }\limits_{N \to \infty } \left( {\frac{{{L^H}\left( N \right)}}{{{L^*}\left( N \right)}} - \left( {aN + b} \right)} \right) = 0\]

Có một trò chơi nổi tiếng ngày xưa với các bạn nhỏ (mình là một ví dụ )

Một bảng gồm 10 ô $1\times 1$ được đánh số mỗi ô từ $0$ đến $9$ như sau (gọi là "trạng thái ban đầu")

\[ \begin{array}{rcl} \boxed{0} & & \\ \boxed{9} & \boxed{8} & \boxed{7}\\ \boxed{6} & \boxed{5} & \boxed{4}\\ \boxed{3} & \boxed{2} & \boxed{1} \end{array}\]

Trên thực tế thì mỗi ô sẽ là một phần bức hình, nhưng để tiện cho mô hình, chúng ta sẽ đánh số như trên. Ngoài ra, ô $\boxed 0$ thực ra là ô trống. Nhưng ta hoàn toàn có thể coi nó là một phần bức hình.

Trong mỗi nước đi, ta được phép đổi chỗ hai ô với điều kiện:

• 2 ô đó có chung 1 cạnh.
• một trong 2 ô là ô $\boxed 0$.

Chẳng hạn, ta được phép đổi chỗ 2 ô $\boxed 0$ và $\boxed 9$ để có được trạng thái sau:

\[ \begin{array}{rcl} \boxed{\color{red} 9} & & \\ \boxed{\color{red} 0} & \boxed{8} & \boxed{7}\\ \boxed{6} & \boxed{5} & \boxed{4}\\ \boxed{3} & \boxed{2} & \boxed{1} \end{array}\]

Nhưng 2 ô $\boxed 2$ và $\boxed 3$ thì không thể đổi cho nhau vì không thỏa điều kiện nước đi (thực ra là không có chỗ trống để di chuyển).

Hỏi, ta có thể đưa được trạng thái sau về trạng thái ban đầu qua một số hữu hạn các nước đi?

Trường hợp 1:

\[ \begin{array}{rcl} \boxed{0} & & \\ \boxed{9} & \boxed{7} & \boxed{8}\\ \boxed{6} & \boxed{5} & \boxed{4}\\ \boxed{2} & \boxed{3} & \boxed{1} \end{array}\]

Trường hợp 2:

\[ \begin{array}{rcl} \boxed{0} & & \\ \boxed{9} & \boxed{7} & \boxed{8}\\ \boxed{6} & \boxed{5} & \boxed{4}\\ \boxed{3} & \boxed{2} & \boxed{1} \end{array}\]

(CASIO THCS toàn quốc năm 2011) Một quả bóng rổ theo tiêu chuẩn quốc tế có dạng hình cầu với bán kính $R = 12,09 (cm)$ (như hình bên). Người ta muốn tạo ra các túi dạng hình hộp đứng có nắp bằng bìa ( cứng và nhẵn ) để đựng được ${\bf 12}$ quả bóng rổ nói trên. Nếu chưa tính cần có các mép dán thì diện tích bìa ít nhất để tạo mội túi như thế là bao nhiêu $cm^2$?

https://diendantoanh...5-đến-năm-2014/

Thầy @thvn nói về các bài toán "căn bản" trong hình học THCS làm mình nhớ ngày xưa có vài bài thú vị cho lớp 6,7

1) Cho tam giác $ABC$ nhọn. Trên $BC$ lấy $D, E$ sao cho $\angle BAD = \angle DAE = \angle EAC$. Trong 3 đoạn thẳng $BD,DE,EC$, đoạn nào dài nhất?

Và bài toán "đảo":

2) Cho tam giác $ABC$ nhọn. Trên $BC$ lấy $D,E$ sao cho $BD=DE=EC$. Trong 3 góc $\angle BAD, \angle DAE, \angle EAC$, góc nào nhỏ nhất?