MathDB

2011 Princeton University Math Competition

Part of Princeton University Math Competition

Subcontests

(28)
Team Round
1

Pumac 2011 Team Round, Sudoku puzzle + Crossword

Time Limit: 25 minutes Maximum Possible Score: 81
The following is a mathematical Sudoku puzzle which is also a crossword. Your job is to fill in as many blanks as you possibly can, including all shaded squares. You do not earn extra points for showing your work; the only points you get are for correctly filled-in squares. You get one point for each correctly filled-in square. You should read through the following rules carefully before starting. ∙\bullet Your time limit for this round is 2525 minutes, in addition to the five minutes you get for reading the rules. So make use of your time wisely. The round is based more on speed than on perfect reasoning, so use your intuition well, and be fast. ∙\bullet This is a Sudoku puzzle; all the squares should be filled in with the digits 11 through 99 so that every row and column contains each digit exactly once. In addition, each of the nine 3×33\times 3 boxes that compose the grid also contains each digit exactly once. Furthermore, this is a super-Sudoku puzzle; in addition to satisfying all these conditions, the four 3×33\times 3 boxes with red outlines also contain each of 1,...,91,..., 9 exactly once. This last property is important to keep in mind – it may help you solve the puzzle faster. ∙\bullet Just to restate the idea, you can use the digits 11 through 99, but not 00. You may not use any other symbol, such as π\pi or ee or ϵ\epsilon. Each square gets exactly one digit. ∙\bullet The grid is also a crossword puzzle; the usual rules apply. The shaded grey squares are the “black” squares of an ordinary crossword puzzle. The white squares as well as the shaded yellow ones count as the “white” crossword squares. All squares, white or shaded, count as ordinary Sudoku squares. ∙\bullet If you obtain the unique solution to the crossword puzzle, then this solution extends to a unique solution to the Sudoku puzzle. ∙\bullet You may use a graphing calculator to help you solve the clues.
The following hints and tips may prove useful while solving the puzzle.
∙\bullet Use the super-Sudoku structure described in the first rule; use all the symmetries you have. Remember that we are not looking for proofs or methods, only for correctly filled-in squares. ∙\bullet If you find yourself stuck on a specific clue, it is nothing to worry about. You can obtain the solution to that clue later on by solving other clues and figuring out certain digits of your desired solution. Just move on to the rest of the puzzle. ∙\bullet As you progress through the puzzle, keep filling in all squares you have found on your solution sheet, including the shaded ones. Remember that for scoring, the shaded grey squares count the same as the white ones.
Good luck!
[asy] // place label "s" in row i, column j void labelsq(int i, int j, string s) { label(""+s+""+s+"",(j-0.5,7.5-i),fontsize(14)); } // for example, use the command // labelsq(1,7,"2"); // to put the digit 2 in the top right box // **** rest of code **** size(250); defaultpen(linewidth(1)); pair[] labels = {(1,1),(1,4),(1,6),(1,7),(1,9),(2,1),(2,6),(3,4),(4,1),(4,8),(5,1),(6,3),(6,5),(6,6),(7,1),(7,2),(7,7),(7,9),(8,1),(8,4),(9,1),(9,6)}; pair[] blacksq = {(1,5),(2,5),(3,2),(3,3),(3,8),(5,5),(5,6),(5,7),(5,9),(6,2),(6,7),(6,9),(8,3),(9,5),(9,8)}; path peachsq = shift(1,1)*scale(3)*unitsquare; pen peach = rgb(0.98,0.92,0.71); pen darkred = red + linewidth(2); fill(peachsq,peach); fill(shift(4,0)*peachsq,peach); fill(shift(4,4)*peachsq,peach); fill(shift(0,4)*peachsq,peach); for(int i = 0; i < blacksq.length; ++i) fill(shift(blacksq.y-1, 9-blacksq.x)*unitsquare, gray(0.6)); for(int i = 0; i < 10; ++i) { pen sudokuline = linewidth(1); if(i == 3 || i == 6) sudokuline = linewidth(2); draw((0,i)--(9,i),sudokuline); draw((i,0)--(i,9),sudokuline); } draw(peachsq,darkred); draw(shift(4,0)*peachsq,darkred); draw(shift(4,4)*peachsq,darkred); draw(shift(0,4)*peachsq,darkred); for(int i = 0; i < labels.length; ++i) label(string(i+1), (labels.y-1, 10-labels.x), SE, fontsize(10)); // **** draw letters **** draw(shift(.5,.5)*((0,6)--(0,8)--(2,8)--(2,7)--(0,7)^^(3,8)--(3,6)--(5,6)--(5,8)^^(6,6)--(6,8)--(7,8)--(7,7)--(7,8)--(8,8)--(8,6)^^(0,3)--(0,5)--(2,5)--(2,3)--(2,4)--(0,4)^^(5,3)--(3,3)--(3,5)--(5,5)),linewidth(1)+rgb(0.94,0.74,0.58)); // **** end rest of code ****[/asy]
Across
1 Across. The following is a normal addition where each letter represents a (distinct) digit: GOT+TO+GO+TO=TOPGOT + TO + GO + TO = TOPThis certainly does not have a unique solution. However, you discover suddenly that G=2G = 2 and P∉{4,7}P \notin \{4, 7\}. Then what is the numeric value of the expression GOT×TOGOT \times TO?
3 Across. A strobogrammatic number which reads the same upside down, e.g. 619619. On the other hand, a triangular number is a number of the form n(n+1)/2n(n + 1)/2 for some n∈Nn \in N, e.g. 1515 (therefore, the ithi^{th} triangular number TiT_i is the sum of 11 through ii). Let aa be the third strobogrammatic prime number. Let bb be the smaller number of the smallest pair of triangular numbers whose sum and difference are also triangular numbers. What is the value of abab?
6 Across. A positive integer mm is said to be palindromic in base ℓ\ell if, when written in base ℓ\ell , its digits are the same front-to-back and back-to-front. For j,k∈Nj, k \in N, let μ(j,k)\mu (j, k) be the smallest base-1010 integer that is palindromic in base jj as well as in basek k, and let ν(j,k):=(j+k)⋅μ(j,k)\nu (j, k) := (j + k) \cdot \mu (j, k). Find the value of ν(5,9)\nu (5, 9).
7 Across. Suppose you have the unique solution to this Sudoku puzzle. In that solution, let XX denote the sum of all digits in the shaded grey squares. Similarly, let YY denote the sum of all numbers in the shaded yellow squares on the upper left block (i.e. the 3×33 \times 3 box outlined red towards the top left). Concatenate XX with YY in that order, and write that down.
8 Across. For any n∈Nn \in N such that 1<n<101 < n < 10, define the sequence Xn,1X_{n,1},Xn,2X_{n,2},... ... by Xn,1=nX_{n,1} = n, and for r≥2r \ge 2, X_{n,r} is smallest number k∈Nk \in N larger than X_{n,r-1} such that kk and the sum of digits of kk are both powers of nn. For instance, X3,1=3X_{3,1 = 3}, X3,2=9X_{3,2} = 9, X3,3=27X_{3,3} = 27, and so on. Concatenate X2,2X_{2,2} with X2,4X_{2,4}, and write down the answer.
9 Across. Find positive integers x,y,zx, y,z satisfying the following properties: yy is obtained by subtracting 9393 from xx, and zz is obtained by subtracting 183183 from yy, furthermore, x,yx, y and zz in their base-1010 representations contain precisely all the digits from 11 through 99 once (i.e. concatenating x,yx, y and zz yields a valid 99-digit Sudoku answer). Obviously, write down the concatenation of x,yx, y and zz in that order.
11 Across. Find the largest pair of two-digit consecutive prime numbers aa and bb (with a<ba < b) such that the sum of the digits of a plus the sum of the digits of b is also a prime number. Write the concatenation of aa and bb.
12 Across. Suppose you have a strip of 2n+12n + 1 squares, with n frogs on the nn squares on the left, and nn toads on the nn squares on the right. A move consists either of a toad or a frog sliding to an adjacent square if it is vacant, or of a toad or a frog jumping one square over another one and landing on the next square if it is vacant. For instance, the starting position https://cdn.artofproblemsolving.com/attachments/a/a/6c97f15304449284dc282ff86014f526322e4a.png has the position https://cdn.artofproblemsolving.com/attachments/e/6/e2c9520731bd94dc0aa37f540c2b9d1bce6432.png or the position https://cdn.artofproblemsolving.com/attachments/3/f/06868eca80d649c4f80425dc9dc5c596cb2a4e.png as results of valid first moves. What is the minimum number of moves needed to swap the toads with the frogs if n=5n = 5? How about n=6n = 6? Concatenate your answers.
15 Across. Let ww be the largest number such that ww, 2w2w and 3w3w together contain every digit from 11 through 99 exactly once. Let xx be the smallest integer with the property that its first 55 multiples contain the digit 99. A Leyland number is an integer of the form mn+nmm^n + n^m for integers m,n>1m, n > 1. Let yy be the fourth Leyland number. A Pillai prime is a prime number pp for which there is an integer n>0n > 0 such that n!≡−1(mod  p)n! \equiv - 1 (mod \,\, p), but p≢1(mod  n)p \not\equiv 1 (mod \,\, n). Let zz be the fourth Pillai prime. Concatenate ww, x,yx, y and zz in that order to obtain a permutation of 1,...,91,..., 9. Write down this permutation.
19 Across. A hoax number k∈Nk \in N is one for which the sum of its digits (in base 1010) equals the sum of the digits of its distinct prime factors (in base 1010). For instance, the distinct prime factors of 2222 are 22 and 1111, and we have 2+2=2+(1+1)2+2 = 2+(1+1). In fact, 2222 is the first hoax number. What is the second?
20 Across. Let a,ba, b and cc be distinct 22-digit numbers satisfying the following properties: – aa is the largest integer expressible as a=xy=yxa = x^y = y^x, for distinct integers xx and yy. – bb is the smallest integer which has three partitions into three parts, which all give the same product (which turns out to be 12001200) when multiplied. – cc is the largest number that is the sum of the digits of its cube. Concatenate a,ba, b and cc, and write down the resulting 6-digit prime number.
21 Across. Suppose N=a‾ b‾ c‾ d‾N = \underline{a}\, \underline{b} \, \underline{c} \, \underline{d} is a 44-digit number with digits a,b,ca, b, c and dd, such that N=a⋅b⋅c⋅d7N = a \cdot b \cdot c \cdot d^7. Find NN.
22 Across. What is the smallest number expressible as the sum of 2,3,42, 3, 4, or 55 distinct primes?
Down
1 Down. For some a,b,c∈Na, b, c \in N, let the polynomial p(x)=x5−252x4+ax3−bx2+cx−62604360p(x) = x^5 - 252x^4 + ax^3 - bx^2 + cx - 62604360 have five distinct roots that are positive integers. Four of these are 2-digit numbers, while the last one is single-digit. Concatenate all five roots in decreasing order, and write down the result.
2 Down. Gene, Ashwath and Cosmin together have 25112511 math books. Gene now buys as many math books as he already has, and Cosmin sells off half his math books. This leaves them with 29192919 books in total. After this, Ashwath suddenly sells off all his books to buy a private jet, leaving Gene and Cosmin with a total of 21842184 books. How many books did Gene, Ashwath and Cosmin have to begin with? Concatenate the three answers (in the order Gene, Ashwath, Cosmin) and write down the result.
3 Down. A regular octahedron is a convex polyhedron composed of eight congruent faces, each of which is an equilateral triangle; four of them meet at each vertex. For instance, the following diagram depicts a regular octahedron: https://cdn.artofproblemsolving.com/attachments/c/1/6a92f12d5e9f56b0699531ae8369a0ab8ab813.png Let TT be a regular octahedron of edge length 2828. What is the total surface area of TT , rounded to the nearest integer?
4 Down. Evaluate the value of the expression ∑k=T24+1T25k,\sum^{T_{25}}_{k=T_{24}+1}k, where TiT_i denotes the ithi^{th} triangular number (the sum of the integers from 11 through ii).
5 Down. Suppose rr and ss are consecutive multiples of9 9 satisfying the following properties: – rr is the smallest positive integer that can be written as the sum of 33 positive squares in 33 different ways. – ss is the smallest 22-digit number that is a Woodall number as well as a base-1010 Harshad number. A Woodall number is any number of the form n⋅2n−1n \cdot 2^n - 1 for some n∈Nn \in N. A base-1010 Harshad number is divisible by the sum of its digits in base 1010. Concatenate rr and ss and write down the result.
10 Down. For any k∈Nk \in N, let ϕp(k)\phi_p(k) denote the sum of the distinct prime factors of kk. Suppose NN is the largest integer less than 5000050000 satisfying ϕp(N)=ϕp(N+1)\phi_p(N) =\phi_p(N + 1), where the common value turns out to be a meager 5555. What isN N?
13 Down. The nthn^{th} ss-gonal number P(s,n)P(s, n) is defined as P(s,n)=(s−3)Tn−1+TnP(s, n) = (s - 3)T_{n-1} + T_n where TiT_i is the ithi^{th} triangular number (recall that the ithi^{th} triangular number is the sum of the numbers 11 through ii). Find the least NN such that NN is both a 3434-gonal number, and a 163163-gonal number.
14 Down. A biprime is a positive integer that is the product of precisely two (not necessarily distinct) primes. A cluster of biprimes is an ordered triple (m,m+1,m+2)(m,m + 1,m + 2) of consecutive integers that are biprimes. There are precisely three clusters of biprimes below 100. Denote these by, say, {(p,p+1,p+2),(q,q+1,q+2),(r,r+1,r+2)}\{(p, p + 1, p + 2), (q, q + 1,q + 2), (r, r + 1, r + 2)\} and add the condition that p+2<q<r−2p + 2 < q < r - 2 to fix the three clusters. Interestingly, p+1p + 1 and qq are both multiples of 1717. Concatenate qq with p+1p + 1 in that order, and write down the result.
16 Down. Find the least positive integer mm (written in base 1010 as m=a‾ b‾ c‾m = \underline{a} \, \underline{b} \, \underline{c} , with digits a,b,ca, b,c), such that m=(b+c)am = (b + c)^a.
17 Down. Let XX be a set containing 3232 elements, and let Y⊆XY\subseteq X be a subset containing 2929 elements. How many 22-element subsets of XX are there which have nonempty intersection with YY?
18 Down. Find a positive integer K<196K < 196, which is a strange twin of the number 196196, in the sense that K2K^2 shares the same digits as 1962196^2, and K3K^3 shares the same digits as 1963196^3.
PS. You should use hide for answers.
A1
1
A6
1
A5 / B8
1
A2 / B4
1
A1 / B3
1
B5
1
A7
2

2011 PUMaC Number Theory A7

Let {gi}i=0∞\{g_i\}_{i=0}^{\infty} be a sequence of positive integers such that g0=g1=1g_0=g_1=1 and the following recursions hold for every positive integer nn: \begin{align*} g_{2n+1} &= g_{2n-1}^2+g_{2n-2}^2 \\ g_{2n} &= 2g_{2n-1}g_{2n-2}-g_{2n-2}^2 \end{align*} Compute the remainder when g2011g_{2011} is divided by 216216.

2011 PUMaC Geometry A7

Let ABCABC be a triangle with AB=2,BC=5,AC=4AB = 2, BC = 5, AC = 4. Let MM be the projection of CC onto the external angle bisector at vertex BB. Similarly, let NN be the projection of BB onto the external angle bisector at vertex CC. If the ratio of the area of quadrilateral BCNMBCNM to the area of triangle ABCABC is a/ba/b, where aa and bb are positive integers and gcd⁡(a,b)=1\gcd(a, b) = 1, find a+ba + b.
A6 / B8
1
A5 / B7
1
A3
2

2011 PUMaC Geometry A3

Let PQPQ and PRPR be tangents to a circle ω\omega with diameter ABAB so that A,Q,R,BA, Q, R, B lie on ω\omega in that order. Let HH be the projection of PP onto ABAB and let ARAR and PHPH intersect at SS. If ∠QPH=30∘\angle QPH = 30^{\circ} and ∠HPR=20∘\angle HPR = 20^\circ, find ∠ASQ\angle ASQ in degrees.

2011 PUMaC Individual Finals A3

Let ABCABC be an equilateral triangle having sides of length 1, and let PP be a point in the interior of ΔABC\Delta ABC such that ∠ABP=15∘\angle ABP = 15 ^\circ. Find, with proof, the minimum possible value of AP+BP+CPAP + BP + CP. (Comment: In fact this question is incorrect, unfortunately. A more reasonable problem: Prove that AP+BP+CP≥3AP + BP + CP \ge \sqrt{3}.)
A2 / B6
1
A4 / B6
2
A3 / B5
2
A2 / B3
1
A1 / B2
2
B4
3

2011 PUMaC Algebra B4

Let ff be an invertible function defined on the complex numbers such that z2=f(z+f(iz+f(−z+f(−iz+f(z+…)))))z^2 = f(z + f(iz + f(-z + f(-iz + f(z + \ldots))))) for all complex numbers zz. Suppose z0≠0z_0 \neq 0 satisfies f(z0)=z0f(z_0) = z_0. Find 1/z01/z_0. (Note: an invertible function is one that has an inverse).

2011 PUMaC Combinatorics B4

A function f:{1,2,…,n}→{1,…,m}f:\{1,2, \ldots, n\} \to \{1, \ldots, m\} is multiplication-preserving if f(i)f(j)=f(ij)f(i)f(j) = f(ij) for all 1≤i≤j≤ij≤n1 \le i \le j \le ij \le n, and injective if f(i)=f(j)f(i) = f(j) only when i=ji = j. For n=9,m=88n = 9, m = 88, the number of injective, multiplication-preserving functions is NN. Find the sum of the prime factors of NN, including multiplicity. (For example, if N=12N = 12, the answer would be 2+2+3=72 + 2 + 3 = 7.)

2011 PUMaC Geometry B4

Let ω\omega be a circle of radius 66 with center OO. Let ABAB be a chord of ω\omega having length 55. For any real constant cc, consider the locus L(c)\mathcal{L}(c) of all points PP such that PA2−PB2=cPA^2 - PB^2 = c. Find the largest value of cc for which the intersection of L(c)\mathcal{L}(c) and ω\omega consists of just one point.
B3
3

2011 PUMaC Algebra B3

Let f(x)=x3−7x2+16x−10f(x) = x^3-7x^2+16x-10. As xx ranges over all integers, find the sum of distinct prime values taken on by f(x)f(x).

2011 PUMaC Geometry B3

Let ABCDABCD be a trapezoid with ADAD parallel to BCBC, AD=2AD = 2, and BC=1BC = 1. Let MM be the midpoint of ADAD, and let PP be the intersection of BDBD with CMCM. Extend APAP to meet segment CDCD at point QQ. If the ratio CQ/QD=a/bCQ/QD = a/b, where aa and bb are positive integers and gcd(a,b)=1\text{gcd}(a, b) = 1, find a+ba + b.

2011 PUMaC Individual Finals B3

In a kk-player tournament for k>1k > 1, every player plays every other player exactly once. Find with proof the smallest value of kk such that it is possible that for any two players, there was a third player who beat both of them.
B2
3

2011 PUMaC Algebra B2

If aa and bb are the roots of x2−2x+5x^2 - 2x + 5, what is ∣a8+b8∣|a^8 + b^8|?

2011 PUMaC Number Theory B2

Two robots are programmed to communicate numbers using different bases. The first robot states: "I communicate in base 10, which interestingly is a perfect square. You communicate in base 16, which is not a perfect square." The second robot states: "I find it more interesting that the sum of our bases is the factorial of an integer." The second robot is referring to the factorial of which integer?

2011 PUMaC Individual Finals B2

Prove for irrational number α\alpha and positive integer nn that (α+α2−1)1/n+(α−α2−1)1/n \left( \alpha + \sqrt{\alpha^2 - 1} \right)^{1/n} + \left(\alpha - \sqrt{\alpha^2 - 1} \right)^{1/n} is irrational.
B1
5
A8
4
A7 / B8
2

2011 PUMaC Algebra A7 / B8

Let α1,α2,…,α6\alpha_1,\alpha_2,\dots,\alpha_6 be a fixed labeling of the complex roots of x6−1x^6-1. Find the number of permutations {αi1,αi2,…,αi6}\{\alpha_{i_1},\alpha_{i_2},\dots,\alpha_{i_6}\} of these roots such that if P(α1,…,α6)=0P(\alpha_1, \dots, \alpha_6) = 0, then P(αi1,…,αi6)=0P(\alpha_{i_1},\dots,\alpha_{i_6}) = 0, where PP is any polynomial with rational coefficients.

2011 PUMaC Combinatorics A7 / B8

At the start of the PUMaC opening ceremony in McCosh auditorium, the speaker counts 9090 people in the audience. Every minute afterwards, either one person enters the auditorium (due to waking up late) or leaves (in order to take a dreadful math contest). The speaker observes that in this time, exactly 100100 people enter the auditorium, 100100 leave, and 100100 was the largest audience size he saw. Find the largest integer mm such that 2m2^m divides the number of different possible sequences of entries and exits given the above information.
A6 / B7
2
A5
2

2011 PUMaC Algebra A5

Let f_1(x) = \frac{1}{x} \text{and}  f_2(x) = 1 - x Let HH be the set of all compositions of the form h1∘h2∘…∘hkh_1 \circ h_2 \circ \ldots \circ h_k, where each hih_i is either f1f_1 or f2f_2. For all hh in HH, let h(n)h^{(n)} denote hh composed with itself nn times. Find the greatest integer NN such that π,h(π),…,h(N)(π)\pi, h(\pi), \ldots, h^{(N)}(\pi) are all distinct for some hh in HH.

2011 PUMaC Combinatorics A5

Let σ\sigma be a random permutation of {0,1,…,6}\{0, 1, \ldots, 6\}. Let L(σ)L(\sigma) be the length of the longest initial monotonic consecutive subsequence of σ\sigma not containing 00; for example, L(2,3,4‾,6,5,1,0)=3, L(3,2‾,4,5,6,1,0)=2, L(0,1,2,3,4,5,6)=0.L(\underline{2,3,4},6,5,1,0) = 3,\ L(\underline{3,2},4,5,6,1,0) = 2,\ L(0,1,2,3,4,5,6) = 0. If the expected value of L(σ)L(\sigma) can be written as mn\frac mn, where mm and nn are relatively prime positive integers, then find m+nm + n.
A4
2
A3 / B6
1
A2
2
A1 / B5
1