Find the number of 4-digit positive integers with all distinct non-zero digits that satisfy the condition that the sum of the first and last digit is greater than or equal to the sum of the middle two digits.
method 1: computer brute force counting
Program output: 1648
ans = []
for n in range(1000,10000):
s = str(n)
if '0' in s:
continue
if len(set(s)) < 4:
continue
a = int(s[0]) + int(s[3])
b = int(s[1]) + int(s[2])
if a >= b:
ans.append(n)
print(len(ans))
;;;;;;;;;
method 2: analytic
The total number of 4-digit zeroless positive integers with distinct digits is 9*8*7*6 = 3024
Let a be the sum of the first and last digits.
Leb b be the sum of the middle two digits.
The number of ways to get a > b must be the same as the number of ways to get b > a.
If the number of ways to get a = b is X, then our answer is
(3024 - X)/2 + X/2 = (3024 + X)/2
Minimum sum of 2 digits is 1+2 = 3
Maximum sum of 2 digits is 8+9 = 17
There are only a few ways to get each sum.
Starting with the sum of zero, the number of ways to make a given sum from 2 distinct single digits, not counting reverse order, is
[0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 4, 3, 3, 2, 2, 1, 1]
The sum of this list is 36.
The number of nonzero elements of this list is 15 = 17-3+1.
Suppose one of a or b = 5. There are 2 ways to get that sum, 1+4 or 2+3. So there is one way to get a=b (not counting permutations).
What about a sum of 9? There are 4 ways to get that sum, so there are 4 choose 2 ways to pick 2 of those.
So replace the elements of the list with the combination of that element taken 2 at a time:
[0, 0, 0, 0, 0, 1, 1, 3, 3, 6, 6, 6, 3, 3, 1, 1, 0, 0]
The sum of this list is 34.
Now account for permutations.
We could swap the pair chosen for a with the pair chosen for b.
We could swap digit 1 for digit 4.
We could swap digit 2 for digit 3.
Three ways to swap: 2^3 = 8.
So there are a total of 34*8 = 272 ways to come out with a=b
(3024 + 272)/2 = 1648 same answer
|
|
Posted by Larry
on 2024-11-04 09:42:21 |
Computer and Analytic
