ứng dụng lý thuyết Toán để giải các bài toán tin
Lê Nguyễn Tuấn Thành
Như các bạn đã biết, toán học có ảnh hưởng rất lớn đến mọi lĩnh vực của cuộc sống. Các
bài tin nếu có được thuật toán dựa trên cơ sở lí thuyết toán học vững chắc sẽ đem lại kết
quả tốt hơn rất nhiều so với các thuật toán khác. Các bạn có thể tìm thấy nhiều bài tin hay
ứng dụng toán học để giải trên các số báo trước. Trong bài viết này tôi sẽ trao đổi thêm
với các bạn một vài bài tin với các thuật toán dựa trên cơ sở toán học. Các thuật toán tôi
đưa ra có thể chưa tối ưu vì vậy rất mong nhận được sự góp ý của các bạn.
Chúng ta hãy bắt đầu bằng bài toán đơn giản sau:
Bài 1: Tìm tất cả các cặp số nguyên dương x,y,z sao cho x
2
+ y
2
= z
2
. 0< x,y,z ≤10000.
Giải:
Đặt Max là giới hạn trên của x,y,z.
Với bài toán này, chúng ta có thể dùng hai vòng lặp x,y lồng nhau rồi kiểm tra nếu x
2
+ y
2
là số chính phương thì ghi nhận kết quả. Để giảm bớt số lần lặp ta sẽ cho y>x, mỗi lần ghi
nhận kết quả ta sẽ phải viết ra hai cặp nghiệm. Ta dùng một biến dem để ghi nhận số cặp
x,y,z thoả mãn. Chương trình chính có thể viết như sau:
for x:=1 to Max-2 do
for y:=x+1 to Max-1 do
if trunc(sqrt(sqr(x)+sqr(y)))=sqrt(sqr(x)+sqr(y)) then
if trunc(sqrt(sqr(x)+sqr(y)))<=Max then
begin
z:=trunc(sqrt(sqr(x)+sqr(y)));

inc(dem);
writeln(’Cach thu’,dem);
write(’ x=’,x,’ y=’,y,’ z=’,z);
writeln;
inc(dem);
writeln(’Cach thu ’,dem);
write(’ x=’,y,’ y=’,x,’ z=’,z);
writeln;
end;
writeln(’Co tat cac’,dem,’ cach’);
Song ta có thể dùng cách khác để giải bài toán này. Các bạn hãy để ý điều kiện thoả mãn
của x,y,z: x
2
+y
2
= z
2
. Đó chính là phương trình Pitago. Nghiệm của phương trình này có
dạng:
x=t*2*m*n
y=t*(m
2
-n
2
)
z=t*(m
2
+n
2
)

Với m,n,t là các số nguyên dương; m,n nguyên tố cùng nhau 1 chẵn,1 lẻ. Các bạn có thể
tìm thấy chứng minh trên trong các tài liệu về số học, ở đây tôi không chứng minh lại. Từ
công thức trên ta có một cách làm khác như sau: Ta đi tìm các giá trị có thể có của m,n,t.
Với mỗi bộ ba số m,n,t ta sẽ được hai cặp nghiệm x,y,z. Giả sử n<m.
Ta có n
2
<M
2
; t ≤ 1 mà t(n
2
+ m
2
) = z ≤ Max→ 2*n
2
< Max
Lại có: t(n
2
+m
2
)=z ≤ Max → m
2
≤ Max-n
2

Với các phân tích như trên khoảng giới hạn của m,n,t đã nhỏ đi rất nhiều.Vấn đề còn lại là
kiểm tra xem m,n có nguyên tố cùng nhau, có 1 chẵn,1 lẻ không. Để làm điều này ta sẽ viết
một hàm tìm Ucln của hai số m,n để kiểm tra tính nguyên tố cùng nhau của m,n.
Còn một vấn đề cần giải quyết trước khi viết chương trình là:
Liệu với hai cặp số m1,n1,t1 và m2,n2,t2 tìm được thì hai cặp nghiệm x1,y1,z1 và x2,y2,z2
có trùng nhau không? Điều này được chứng minh như sau:

Chứng minh.
Giả sử tồn tại hai cặp số nguyên dương khác nhau m1,n1,t1 và m2,n2,t2 cho ta hai nghiệm
x1,y1,z1 và x2,y2,z2 trùng nhau. Ta sẽ chứng minh điều giả sử là sai.
Thật vậy: do z được tính theo x,y nên ta xét hai trường hợp:
Th1: x1=x2 và y1=y2
Th2: x1=y2 và y1=x2
*) Trường hợp 1
x1=x2 → t1*m1*n1=t2*m2*n2 (1)
y1=y2 → t1*(m1
2
− n1
2
)= t2*(m2
2
− n2
2
) (2)
→ z1=z2 → t1*(m1
2
+ n1
2
)= t2*(m2
2
+ n2
2
) (3)
Từ (2),(3) → t1*m1
2
= t2*m2
2

(4)
và t1*n1
2
= t2*n2
2
(5)
+ Nếu t1=t2 thì từ (4),(5) → m1=m2 và n1=n2
Như vậy hai bộ m1,n1,t1 và m2,n2,t2 trùng nhau (Vôlý)
+ Nếu t1<>t2. Giả sử t1<t2 → t2>1
- nếu t1=1, gọi d là ước nguyên tố bất kì của t2. Từ (4) (5) → m1,n1 cùng chia hết cho d
(Trái với điều kiện của m,n)
- nếu t1<1, gọi d=(t1,t2) đặt t1=t1/d,t2=t2/d → t2<1. Gọi d1 là ước nguyên tố bất kì của t2.
Từ (4),(5) → m1,n1 cùng chia hết cho d1 (Vô lí).
*) Trường hợp 2
x1=y2 → t1*2*m1*n1= t2*(m2
2
− n2
2
) (6)
y1=x2 → t1*(m1
2
− n1
2
)= t2*2*m2*n2 (7)
→ z1=z2 → t1*(m1
2
+ n1
2
)= t2*(m2
2

+ n2
2
) (8)
Từ (6) → t2 chia hết cho 2 do m,n khác tính chẵn lẻ.
Đặt t2=2
n
*t (t không chia hết cho 2).
Từ (8) → t1=2
n
*k (k không chia hết cho 2)
Nhưng từ (6) → t2*(m2
2
− n2
2
) chia hết cho 2
n
nhưng không chia hết cho 2
n+1
còn
t1*2*m1*n1 lại chia hết cho 2
n+1
(Mâu thuẫn).
Như vậy bài toán được chứng minh.
Sau đây là chương trình với cách làm vừa phân tích ở trên:
uses crt;
const max=10000;
var m,n,k,dem,x,y,z:word;
time:longint;
{************************************************}
{Tìm ước chung lớn nhất của hai số nguyên dương a,b}

function ucln(a,b:word):word;
var du:word;
begin
ucln:=1;
if (a=1) or (b=1) then exit;
if a mod b=0 then begin ucln:=b; exit; end;
if b mod a=0 then begin ucln:=a; exit; end;
while b<0 do
begin
du:=a mod b;
a:=b;
b:=du;
end;
ucln:=a;
end;
{************************************************}
BEGIN
clrscr;
dem:=0;
time:=meml[0:$46c];
for n:=1 to trunc(sqrt(max/2)) do
for m:=n+1 to trunc(sqrt(max-sqr(n))) do
if ((m-n) mod 2=1) and (ucln(m,n)=1) then
for k:=1 to max div (sqr(m)+sqr(n)) do
begin
x:=k*2*m*n;
y:=k*(sqr(m)-sqr(n));
z:=k*(sqr(m)+sqr(n));
inc(dem);
writeln(’Cach thu ’,dem);

write(’ x=’,x,’ y=’,y,’ z=’,z);
writeln;
inc(dem);
writeln(’Cach thu’,dem);
write(’ x=’,y,’ y=’,x,’ z=’,z);
writeln;
end;
writeln(’Co tat cac ’,dem,’ cach’);
writeln(’Thoi gian tinh: ’,(meml[0:$46c]-time)/18.2:0:10,’ giay’);
readln;
END.
Các bạn có thể dùng hàm tính thời gian Meml[0:$46C] để so sánh hai cách làm. Tất nhiên
với bài toán đơn giản này thì sự khác biệt là không lớn lắm nhất là với Max nhỏ. Nhưng
qua đó các bạn cũng có thể thấy được hiệu quả việc áp dụng toán học vào trong các bài tin.
Bài 2: Tìm tất cả các số N có 5 chữ số sao cho 2*N cũng có 5 chữ số và tất các chữ số từ 0
đến 9 đều có mặt trong N và 2*N.
Giải:
Đây cũng là một bài toán khá đơn giản, các bạn có thể dùng quay lui để giải 1 cách dễ
dàng, sự chênh lệch về thời gian trong những cài đặt khác nhau là không đáng kể. Nhưng
điều tôi muốn nói khi đưa ra bài này là: các bạn hãy thử phân tích bài toán để tìm ra những
điều kiện nhằm làm giảm bớt qúa trình quay lui.
Trước hết ta có thể thấy để N, 2*N là số có 5 chữ số thì chữ số hàng vạn của N phải lớn
hơn 0 và nhỏ hơn 5. Thứ hai để các chữ số từ 0 đến 9 đều có mặt trong N và 2*N thì chữ
số hàng đơn vị của N phải khác 0. Thứ ba, ta thấy nếu trong N có chứa số 9 và liền trước
số 9 là một số lớn hơn 4 (dạng 9a với a>4) thì trong 2*N cũng sẽ có số 9, tương tự trong N
có chứa số 0 và liền trước số 0 là một số nhỏ hơn 5 (dạng 0a với a<5) thì trong 2*N cũng
có số 0.
Với ba nhận xét trên, ta có cách làm như sau: Dùng một mảng một chiều a: array [1..5] of
0..9 để lưu các chữ số của N (a[1] ứng với chữ số hàng đơn vị). Sau đó dùng quay lui để
xét các trường hợp có thể có của các chữ số trong N. Chú ý nên dùng một mảng để đánh

dấu những chữ số đã xuất hiện trong quá trình quay lui. Để làm được điều này, ta thấy rằng
khi nhân một số với 2 thì nhớ nếu có từ một hàng lên hàng liền sau chỉ có thể là 1.Vì vậy
trong quá trình quay lui ta có thể biết được những chữ số nào đã xuất hiện trong N và 2*N
mà không cần phải đợi đến khi tìm đủ 5 chữ số của N.
Các bạn có thể tham khảo chương trình dưới đây. Hàm kt(j,i) để kiểm tra xem j có thể chọn
vào vị trí thứ i của mảng a không?
uses crt;
type mt1 = array[1..5] of 0..9;
mt2 = array[0..9] of boolean;
var a : mt1;
đ : mt2;
dem : word;
time: longint;
{************************************************}
function kt(j,i:byte):boolean;
var kt1:boolean;
begin
if a[i-1]>=5 then
begin
kt1:=đ[(2*j+1) mod 10];
if j=9 then kt1:=false;
end
else
begin
kt1:=đ[(2*j) mod 10];
if j=0 then kt1:=false;
end;
kt:=kt1;
end;
{************************************************}

procedure viet;
var i:byte;
begin
if a[5]>=5 then exit;
if a[5]=0 then exit;
write(’’);
for i:=5 downto 1 do
write(a[i]);
writeln;
inc(dem);
end;
{************************************************}
procedure try(i:byte);
var j:byte;
begin
for j:=0 to 9 do
if đ[j] and kt(j,i) then
begin
đ[j]:=false;
a[i]:=j;
if a[i-1]>=5 then đ[(2*j+1) mod 10]:=false
else đ[(2*j) mod 10]:=false;
if i=5 then viet
else try(i+1);
đ[j]:=true;
if a[i-1]>=5 then đ[(2*j+1) mod 10]:=true
else đ[(2*j) mod 10]:=true;
end;
end;
{************************************************}

procedure main;
var i:byte;
begin
dem:=0;
for i:=1 to 9 do
begin
fillchar(a,sizeof(a),0);
fillchar(đ,sizeof(đ),true);
a[1]:=i;
đ[i]:=false;