Để một số chia hết cho 3, tổng các chữ số của số đó phải chia hết cho 3. Vì vậy, ta chỉ cần chọn 3 chữ số sao cho tổng của chúng chia hết cho 3.

Có 4 chữ số để chọn: 0, 1, 4, 5.

Có thể chọn 3 chữ số theo các cách sau:
1. 0, 1, 4: Có 3 số tự nhiên có 3 chữ số khác nhau là 104, 140, 410.
2. 0, 1, 5: Có 3 số tự nhiên có 3 chữ số khác nhau là 105, 150, 501.
3. 0, 4, 5: Có 3 số tự nhiên có 3 chữ số khác nhau là 405, 450, 504.
4. 1, 4, 5: Có 6 số tự nhiên có 3 chữ số khác nhau là 145, 154, 415, 451, 514, 541.

Vậy có tổng cộng 3 + 3 + 3 + 6 = 15 số tự nhiên có 3 chữ số khác nhau mà mỗi số đều chia hết cho 3.