Backtrack Problems

Design a backtracking algorithm for generating all bit strings of length n that do not have two consecutive 0s. Compute the complexity of the algorithm.
Solution

Độ phức tạp thuật toán

Tóm tắt lại:
- Big-O , Omega, Theta đều là $\lim n\to \infty$
- Big-O của $f(n)$ là $g(n)$ khi: $f(n)\le C. g(n)$
- Big-Omega của f(n) là g(n) khi: $f(n)\ge C. g(n)$
- Big-Theta của f(n) là g(n) khi: $C1 .g(n) \le f(n) \le C2. g(n)$
a) Với mọi số thực $x$ kí hiệu $\left \lfloor x \right \rfloor$ là số nguyên lớn nhất nhỏ hơn hoặc bằng $x$, chứng minh rằng $\left \lfloor n^2/3 \right \rfloor=\Theta (n^2),$ trong đó $n$ là số nguyên không âm.

Đề thi và lời giải VMO 2016

Ngày 1.

Thời gian làm bài : 180 phút (không kể thời gian giao đề)
Ngày thi thứ nhất:6/1/2016

Bài 1 (5 điểm). Giải hệ phương trình:$\left\{\begin{matrix}6x-y+z^2=3 & & & \\ x^2-y^2-2z=-1 & & & \\ 6x^2-3y^2-y-2z^2=0 & & & \end{matrix}\right.(x,y,z\in\mathbb{R})$

Bài 2 (5 điểm).

a)Cho dãy số $a(n)$ xác định bởi $a_{n}=\ln(2n^2+1)-\ln(n^2+n+1)$ với $n=1,2...$.Chứng minh chỉ có hữu hạn số $n$ sao cho $\left \{ a_{n} \right \}< \frac{1}{2}$

b)Cho dãy số $b(n)$ xác định bởi $b_{n}=\ln(2n^2+1)+\ln(n^2+n+1)$ với $n=1,2...$.Chứng minh tồn tại vô hạn số $n$ sao cho $\left \{ b_n \right \}<\frac{1}{2016}$

Bài 3 (5 điểm). Cho tam giác $ABC$ có $B,C$ cố định,$A$ thay đổi sao cho tam giác $ABC$ nhọn.Gọi $D$ là trung điểm của $BC$ và $E,F$ tương ứng là hình chiếu vuông góc của $D$ lên $AB,AC$

a)Gọi $O$ là tâm của đường tròn ngoại tiếp tam giác $ABC$.$EF$ cắt $AO$ và $BC$ lần lượt tại $M$ và $N$.Chứng minh đường tròn ngoại tiếp tam giác $AMN$ đi qua điểm cố định

b)Các tiếp tuyến của đường tròn ngoại tiếp tam giác $AEF$ tại $E,F$ cắt nhau tại $T$.Chứng minh $T$ thuộc đường thẳng cố định

Bài 4 (5 điểm). Người ta trồng hai loại cây khác nhau trên một miếng đất hình chữ nhật kích thước $m\times n$ ô vuông (mỗi ô trồng một cây).Một cách trồng được gọi là ấn tượng nếu như:

i)Số lượng cây được trồng của hai loại cây bằng nhau

ii)Số lượng chênh lệnh của hai loại cây trên mỗi hàng không nhỏ hơn một nửa số ô của hàng đó và số lượng chênh lệnh của hai loại cây trên mỗi cột không nhỏ hơn một nửa số ô của cột đó

a)Hãy chỉ ra cách trồng ấn tượng khi $m=n=2016$

b)Chứng minh nếu có một cách trồng ấn tượng thì cả $m$ và $n$ đều là bội của $4$

Hỏi cần lấy mẫu với kích thước thích hợp bao nhiêu

Một khách sạn lớn muốn ước lượng tỷ lệ khách có nhu cầu nghỉ trọ nhiều hơn 1 ngày. Họ muốn có độ tin cậy 96% và sai số không quá 5%. Hỏi cần lấy mẫu với kích thước thích hợp bao nhiêu. Nếu chưa có bất kì thông tin nào về phép ước lượng này.
Giải

Không gian Metric và Topo đại cương.

Một số kiến thức mở đầu về Không gian Metric.(part 1)

Bài tập phân phối đều

Giả sử xe bus A chỉ ghé trạm đón khách trong khoảng thời gian 7h đến 7h30 và thời điểm ghé là một biến ngẫu nhiên có phân phối đều. Nếu bạn đến trạm lúc 7h5 thì xác suất bạn phải chờ bus A không quá 10 phút là bao nhiêu?

Đề giải tích 1 năm học 2014-2015

Đề - đáp án giải tích 1 khoa  năm học 2014-2015

Lưu ý: Lời giải chỉ mang tính chất tham khảo, không phải là đáp án chính thức !!!!

Bài 1 (3 đ) Tính các giới hạn
a) $$\lim\limits_{x\to 0}\frac{\ln(1+x)-x}{x^2}$$
b) $$\lim\limits_{x\to +\infty} \frac{x\arctan x}{x^2+1}$$

Cách dùng máy tính để giải toán thống kê

Cách dùng máy tính để giải toán thống kê

Máy tính casino FX-570ES

Các bạn có thể dùng máy tính bỏ túi FX – 570ES để thực hiện nhập dữ liệu bảng thống kê mẫu và tính toán như sau:

Lưu ý: Dấu “–>” chỉ bước tiếp theo phải thực hiện, dấu ‘=’ để nhận số liệu.

Mã Morse

Mã Morse

Mã Morse hay mã Moóc-xơ là một loại mã hóa ký tự dùng để truyền các thông tin điện báo. Mã Morse dùng một chuỗi đã được chuẩn hóa gồm các phần tử dài và ngắn để biểu diễn các chữ cái, chữ số, dấu chấm, và các kí tự đặc biệt của một thông điệp. Các phần từ ngắn và dài có thể được thể hiện bằng âm thanh, các dấu hay gạch, hoặc các xung, hoặc các kí hiệu tường được gọi là "chấm" và "gạch" hay "dot" và "dash" trong tiếng Anh.

Mật mã Vigenère

Mật mã Vigenère

Mật mã Vigenère là một phương pháp mã hóa văn bản bằng cách sử dụng xen kẽ một số phép mã hóa Caesar khác nhau dựa trên các chữ cái của một từ khóa. Nó là một dạng đơn giản của mật mã thay thế dùng nhiều bảng chữ cái.

Tuyển tập Bộ 3 câu phân loại trong các đề thi thử THPT Quốc gia 2015 môn toán

Xuất phát từ thực tế kì thi THPT Quốc gia 2015, với các bạn sử dụng kết quả môn Toán để xét tuyển đại học, thì sự cạnh tranh chủ yếu diễn ra ở bộ ba câu phân loại. Bộ ba câu này thường rơi vào các chủ đề Phương trình - Bất phương trình - Hệ phương trình, Hình học tọa độ phẳng, Bất đẳng thức - Tìm GTLN, GTNN.

ỨNG DỤNG SỐ MŨ LỚN NHẤT CỦA THỪA SỐ NGUYÊN TỐ TRONG CÁC BÀI TOÁN SỐ HỌC

ỨNG DỤNG SỐ MŨ LỚN NHẤT CỦA THỪA SỐ NGUYÊN TỐ

TRONG CÁC BÀI TOÁN SỐ HỌC

Lê Trần Nhạc Long - THPT Chuyên Lê Quý Đôn- Đà Nẵng

----------------------------------------

17/1/2012 Tặng diễn đàn VMF nhân dịp sinh nhật 8 năm của diễn đàn

ĐỀ THI VMEO IV THÁNG 10

ĐỀ THI VMEO IV THÁNG 10

CẤP TRUNG HỌC CƠ SỞ

Bài 1:

Cho $\alpha$ là số thực thỏa mãn $\alpha^3=\alpha+1$. Hãy xác định tất cả các bộ tứ hữu tỉ $(a,b,c,d)$ thỏa mãn $$a\alpha^2+b\alpha+c=\sqrt d$$

Hãy chứng minh tập $\{|\}$ và $\{\downarrow \}$ là đầy đủ trong đại số boole.

Ta định nghĩa phép toán $|$ (hay NAND) và phép toán $ \downarrow $ (hay NOR) như sau:

$1|1=0,1|0=0|1=0|0=1$ và $1\downarrow  1=1\downarrow 0=0\downarrow 1=0,0\downarrow 0=1$

Hãy chứng minh tập $\{|\}$ và $\{\downarrow \}$ là đầy đủ trong đại số boole.

Chứng minh rằng nếu $G$ là đồ thị đơn phân đôi có $v$ đỉnh và $e$ cạnh khi đó $e\le \frac{v^2}{4}$.

Chứng minh rằng nếu $G$ là đồ thị đơn phân đôi có $v$ đỉnh và $e$ cạnh khi đó $e\le \frac{v^2}{4}$.

Tính số bộ $(x_1,x_2,...,x_{m+n})$ thỏa mãn đồng thời các điều kiện sau

Cho $m,n$ là các số nguyên dương mà $m\ge n$.Tính số bộ $(x_1,x_2,...,x_{m+n})$ thỏa mãn đồng thời các điều kiện sau

$\text{i)}$   $x_i\in \left \{ -1,1 \right \}\ \ ,\forall i=\overline{1,m+n}$

$\text{ii)}$  $\sum_{i=1}^k x_i\ge 0\ \ ,\forall k=\overline{1,m+n}$

$\text{iii)}$ $\sum_{i=1}^{m+n}x_i=m-n$

Cho dãy $u_{n+1}\le u_n+u_n^2$ . Chứng minh rằng $\lim\limits_{n\to +\infty}n.u_n=0$

Cho dãy số dương $\{u_n\},n\in \mathbb{N}$ thỏa mãn các điều kiện
1. $u_{n+1}\le u_n+u_n^2$.
2. Tồn tại hằng số $M>0$ sao cho $\sum\limits_{k=1}^n u_k\le M \forall n\in \mathbb{N}$.
Chứng minh rằng $\lim\limits_{n\to +\infty}n.u_n=0$

Tìm đa thức có hệ số thực thỏa mãn điều kiện

Tìm đa thức có hệ số thực thỏa :
i) $degP(x)\geq 1$
ii) $(x+1)(x^2-3)P^{''}(x)-(x^2+x)P'(x)+3P(x)=0$
iii) $P(1)=6$

Arp-Mac

ARP-MAC

Chuyên đề Đa thức Chebyshev

Đa thức Chebyshev là 1 mối liên kết đẹp giữa đại số và lượng giác.Tuy trong các kì thi Olympic gần đây, đa thức Chebyshev ít được xuất hiện vì hệ thống bài tập mang tính chất liên quan lí thuyết của nó, nhưng việc hiểu biết và nghiên cứu đa thức Chebyshev vẫn là một chủ đề rất được quan tâm khi dạy và học toán Olympic. Trong bài viết này chúng tôi sẽ hệ thống lại những tính chất quen thuộc của đa thức Chebyshev, một số ví dụ ứng dụng và hướng phát triển của những bài tập xung quanh đó. 

Qua chuyên đề mong các bạn có thể hiểu thêm về đa thức Chebyshev và say mê học toán hơn.

Down load tại đây.