How many 2021-digit numbers can be formed from 1, 2, 3, 4, 5 and is divisible by 3 (possible repetit

Cooper Doyle

Cooper Doyle

Answered question

2022-07-03

How many 2021-digit numbers can be formed from 1, 2, 3, 4, 5 and is divisible by 3 (possible repetition).
So i have one approach to the problem. I used pigeon hole theorem to prove that there are at least [ 2021 5 ] + 1 = 405 identical number. And since 405 is divisible by 3 so the sum of those 405 same digit is also divisible by 3 and i only need to solve the problem with 2021 405 = 1616-digit numbers. I continued that until there is less than 3 identical digit (the number of identical digits must be divisible by 3). At that point, the problem can be converted to
How many 8-digit numbers can be formed from 1, 2, 3, 4, 5 and is divisible by 3 (possible repetition).
To solve the above problem, i tried to find all 3x for 5 1 3 x 5 5 and solve every custom sub-problem. But my solution seems to be too tedious and i wonder if there is a specific formula to solve the first problem. Every idea is appreciated. Thanks in advance.
I also want to know if there is a way to solve this problem
Share m candy bars to n people such that no one have more than k candy bars.
That sub-problem can help solve my problem.

Answer & Explanation

Melina Richard

Melina Richard

Beginner2022-07-04Added 14 answers

Step 1
Disclaimer
This is only an alternative solution to those provided in the comment section
Solution
We define vectors x i as a vector containing the number of i digits number that are 0, 1, 2 in modulo 3 respectively. From the problem statement we get:
x 1 = { 1 2 2 }
An n + 1 digits number is divisible by 3 if the first digit is 0 in modulo 3 and the last n digits form a number that is 0 in modulo 3, the first digit is 1 in modulo 3 and the last n digits form a number that is 2 in modulo 3, or the first digit is 2 in modulo 3 and the last n digits form a number that is 1 in modulo 3. Apply similar logic to n + 1 digits number that is 1 and 2 in modulo 3 to obtain the following recurrence - relations:
x n + 1 = [ 1 2 2 2 1 2 2 2 1 ] × x n
From here, it's easy to show the following is true:
x n + 1 = [ 1 2 2 2 1 2 2 2 1 ] n { 1 2 2 }
Step 2
Using eigenvectors and eigenvalues we have:
x n + 1 = [ 1 1 1 1 0 1 0 1 1 ] [ ( 1 ) n 0 0 0 ( 1 ) n 0 0 0 5 n ] [ 1 3 2 3 1 3 1 3 1 3 2 3 1 3 1 3 1 3 ] { 1 2 2 }
The final result is
x n = 1 3 { 5 n + 2 ( 1 ) n 5 n ( 1 ) n 5 n ( 1 ) n }
Therefore the number of n digits number with such digits that are divisible by 3 is given by 5 n + 2 ( 1 ) n 3 .

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?