Brainsteem #4 Prize Maths Puzzle - Factorials [free 3SBD]
This question has been created based on the level expected at a Junior Olympiad competition or a national challenge. It can, of course, be enjoyed at any level!
Your aim is to find all the solutions (a, b), such that 13 > a > b, that solve the equation,
where N is a multiple of 13.
As is standard, a! = a.(a-1).(a-2)... 3.2.1.
Hint. Without giving away the solution, the skill here is in reducing dramatically the number of combinations of a and b so that you can focus on a quick method of enumeration. In a competition, such questions are expected to be done without even a calculator.
As always, the top prize requires a full solution and a brief method of the steps taken.
Any questions, just ask!
The Prizes
Earnings from each Brainsteem Puzzle will go towards the next Prizes.
For this Brainsteem # 4 the Prizes are:
2 SBD for the first correct answer that includes a valid method
1 SBD for one other correct answer that will be chosen randomly. That means you can still win this prize even if the answer may already be visible!
As these are maths problems, a little bit about the randomising process for the extra prizes. Every comment with a correct answer is placed in rank order using the timestamp. The probability of winning is then inversely proportional to the order in which answers are posted. It isn't that complicated! I'll write a post about it soon! For example, if only 4 people answer they are ranked 1, 2, 3 and 4. The ratios of their probabilities of winning the random prize become 12 : 6 : 4 : 3. The actual probabilities are then approximately 0.48 : 0.24 : 0.16 : 0.12. Easy! It is possible for the same person to win both prizes.
Please upvote! Resteem if you think this is a great puzzle! I will upvote all correct answers and any other interesting comments. To be fair to everyone, the prize closes after 7 days. Winners will be notified after that date and usernames posted with a solution.
Enjoy!
this is a really tough question.... I will show you what I have done so far
a!+b! = b! ( a(a-1)(a-2)...(b+1) + 1) which is divisible by 13
however b! cannot be divisible by 13
so a(a-1)(a-2)...(b+1) + 1 is divisible by 13
which means that a(a-1)(a-2)...(b+1) = 12 (mod 13)
i can think of the solutions: 4 * 3 = 12 (mod 13)
i.e. (2,4) is an answer
and also 12 = 12 (mod 13)
i.e. (12,11) is an answer
I guess there are some more but I am stuck here...
Yes, that's a good start. How can one be sure to have cycled through every combination?
I can't think of, coz 12 (mod 13) have infinitely many congruent values, like 12 = 25 = 38 = 51 .... (mod 13)
Each of these have a possibility to give a valid answer
For example, 90 = 12 (mod 13), where 90 can be written as 10 x 9. So I just found another pair: (10,8)
But this process can be continued infinitely!
mmm... I think you've complicated the question. Try the whole thing in mod13 so you're looking for zeros. There are various solutions but certainly enumerable fairly quickly.
Ok let me try again...
So a!+b! = 0 (mod 13), then a! (mod 13) + b! (mod 13) = 0 (mod 13)
here is a list of factorials mod 13:
1! 1
2! 2
3! 6
4! 11
5! 3
6! 5
7! 9
8! 7
9! 11
10! 6
11! 1
12! 12
So we should pick the pairs that sum to 13. We can obtain (1,12), (11,12), (2,4), (2,9), (3,8), (8,10).
you missed the pair (0,12) because 0! is also 1
Very good! the question did not limit the answers to positive integers.
You are right, thanks for pointing this out :)
Processing this a little late!
Winner is @cryptoriddler - you may claim either 2 SBD or a free randowhale vote. Please let know within 2 days or will process the payment in SBD,
Second prize of 1 SBD to @kenchung - money on its way!
thanks, I got the money already! please keep organizing these challenges, really fun :)
My solutions:
(0,12),(1,12),(2,4),(2,9),(3,8),(8,10),(11,12)
As I actually learn python, i solved it the brute force way ;)
output:
find all the solutions (a, b), such that 13 > a > b, that solve the equation,
N = a! + b! , where N is a multiple of 13.
my list is
4,2
8,3
9,2
10,8
12,1
12,11
assuming 5!=5x4x3x2x1, 4!=4x3x2x1, etc.
Yes, good. Sorry, noticed that the asterisks * are used as Markdown codes so made the factorials look a mess!
"As is standard, a! = a.(a-1).(a-2)... 3.2.1."
is this supposed to be A! =Ax(A-1)x(A-2)... 3! = 3x2x1?
Ok let me try again...
So a!+b! = 0 (mod 13), then a! (mod 13) + b! (mod 13) = 0 (mod 13)
here is a list of factorials mod 13:
1! 1
2! 2
3! 6
4! 11
5! 3
6! 5
7! 9
8! 7
9! 11
10! 6
11! 1
12! 12
So we should pick the pairs that sum to 13. We can obtain (1,12), (11,12), (2,4), (2,9), (3,8), (8,10).