Oh yah! You made it to the final day of the puzzle solving event! However, math week is not over yet. In fact, the big, in-person event in happening on Friday (March 7)! Check out the event planning page for more details.
To conclude our problem solving tournament, we will be giving you three number theory puzzles today. Number theory is just the study of numbers! To be precise, whole numbers (integers).
If you are able to solve any of the puzzles, submit your solution by Thursday March 7, 11:25am to win a treat! Additionally, the first solver of each puzzle gets a bonus!
Puzzle 1 - Password
I forgot my password. As a math enthusiast, I only remember that the password is:
- A 5-digit whole number
- A palindrome. That means this number reads the same left to right and right to left. For instance, \(1283821\) is a palindrome.
- A multiple of \(11\).
- A multiple of \(72\).
- A perfect square. That means it is the square of some other integer. For example, \(16\) and \(81\) are perfect squares.
Can you tell me what my password is?
Puzzle 2 - Chicken McNuggets
I love McDonald’s McNuggets. They are especially suitable for parties, because each nugget is bite size. And during the party, it is so popular that everyone would fight for the last piece of nugget.
I’d like to be fair to all my friends, so I will purchase exactly \(2\) nuggets for each of my friends. Unfortunately, the McDonald’s near my home only offers Chicken McNuggets in packs of \(6\) and \(10\).
I discovered that when I have a big party, I can always figure out a way to purchase the nuggets so that the number of nuggets I get is exactly the number I need. For example, if \(23\) friends are invited, then I need \(46\) nuggets. I can buy \(4\) packs of \(10\) and \(1\) pack of \(6\) to fulfill that. However, if the party is small, I sometimes can not purchase the nuggets accurately. An example is, if only \(4\) friends are coming, then \(8\) nuggets are needed, which can’t be fulfilled exactly using packs of \(6\) and \(10\).
What is the largest number of friends I can invite to my party, such that I cannot purchase exactly that number of nuggets I need for the party?
Puzzle 3 - “Phi” Week
As we all know \(\pi\) is a Greek letter that represents the ratio of a circle’s circumference to its diameter, which is also the theme of this math week.
\(\varphi\) (also written as \(\phi\)) is another Greek letter, written as “phi” in English. In the field of number theory, it often refers to a function: \(\varphi(n)\) for some positive integer \(n\) is the number of positive integers less than \(n\) that are relatively prime to \(n\). Two integers are relatively prime if they don’t have a common divisor other than \(1\). For example, \(\varphi(6) = 2\) because only \(1\) and \(5\) are relatively prime to \(6\) among all positive integers less than \(6\).
Subtask 1
Let \(p\) and \(q\) be prime numbers such that \(p \neq q\). Express \(\varphi(pq)\) in terms of \(p\) and \(q\).
Subtask 2
Let \(n\) be a positive integer and \(p\) be a prime number. Express \(\varphi(p^{n})\) in terms of \(p\) and \(n\).