Number theoryDifficulty 6.3National olympiadProve it
Let a and b be positive integers such that a!b! is a multiple of a!+b!. Prove that 3a⩾2b+2. (United Kingdom)
Solution
If a>b, we immediately get 3a⩾2b+2. In the case a=b, the required inequality is equivalent to a⩾2, which can be checked easily since (a,b)=(1,1) does not satisfy a!+b!∣a!b!. We now assume a>b. We observe that c!∣M since M is a product of c consecutive integers. Thus gcd(1+M,c!)=1, which implies 1+Mc!a!=(c+1)(c+2)⋯a If a⩽2c, then c!a! is a product of a−c⩽c integers not exceeding a whereas M is a product of c integers exceeding a. Therefore, 1+M>c!a!, which is a contradiction. It remains to exclude the case a=2c+1. Since a+1=2(c+1), we have c+1∣M. Hence, we can deduce from (1) that 1+M∣(c+2)(c+3)⋯a. Now (c+2)(c+3)⋯a is a product of a−c−1=c integers not exceeding a; thus it is smaller than 1+M. Again, we arrive at a contradiction. Comment 1. One may derive a weaker version of (1) and finish the problem as follows. After assuming a⩽2c+1, we have ⌊2a⌋⩽c, so ⌊2a⌋!M. Therefore, 1+M(⌊2a⌋+1)(⌊2a⌋+2)⋯a Observe that (⌊2a⌋+1)(⌊2a⌋+2)⋯a is a product of ⌈2a⌉ integers not exceeding a. This leads to a contradiction when a is even since ⌈2a⌉=2a⩽c and M is a product of c integers exceeding a. When a is odd, we can further deduce that 1+M(2a+3)(2a+5)⋯a since ⌊2a⌋+1=2a+1a+1. Now (2a+3)(2a+5)⋯a is a product of 2a−1⩽c numbers not exceeding a, and we get a contradiction.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: NuminaMath-1.5,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.