How many positive integers less than or equal to are there for which the sum of digits of is the same as the sum of digits of ?
Solution
does not satisfy the requirement, so let us consider only positive integers . One can represent such an integer in the form where are 1-digit non-negative integers. Since the number obtained by multiplying a 1-digit integer by is at most and its one's digit is either or , we see that there is no carry-over in the addition . Hence if , then . Furthermore, if is an even 1-digit number, then , while if is an odd 1-digit number, then . Therefore, if for a positive integer less than or equal to , then , where is the number of odd integers among the one's, ten's and hundred's digits of .
The remainder one gets when one divides a positive integer by equals the remainder one gets when is divided by . Hence if , then must be a multiple of . There are multiples of less than or equal to . We will find, by grouping them into sub-classes and checking, how many numbers among these will not satisfy the condition .
(1) When .
Since , where is the number of integers among the one's, ten's and hundred's digits of , must be if in this class satisfies . Consequently, among those 's in this class which do not satisfy the requirement have a representation corresponding with given by and their permutations, and there are exactly such numbers.
(2) When .
Among 's in this class those which satisfy the requirement have exactly odd integers among their one's, ten's and hundred's digits. If one such is written as , then the number belongs to the class (1) and satisfies the requirement, and conversely, if is a number belonging to the class (1), which satisfies the requirement, then belongs to class (2) and satisfies the requirement. Thus, there is a one-to-one correspondence between elements of class (1) and those of class (2), and the correspondence preserves the validity of the requirement. Therefore, as in class (1) there are numbers in class (2) which do not satisfy the requirement.
There is only the number belonging to this class, and this number satisfies the requirement.
Thus, among the multiples of , there are numbers which do not satisfy the requirement, and hence there are exactly positive integers less than or equal to for which .