0 0

By admin 数学代写 2022年2月2日

1. Stanford University Mathematics Camp (SUMaC) 2022 Admissions Exam

For use by SUMaC 2022 applicants only. Not for distribution.

Tell us something interesting about the number 2022 or explain why you think it is a completely uninteresting number. This is a purely subjective open-ended question with no wrong answers.
A number $n$ has the increasing factor property if it can be uniquely factored into a product of strictly increasing factors, not including the factorization $n=1 \cdot n$. That is, $n=n_{1} \cdot n_{2} \cdots \cdots n_{k}$ for $k>1$ and $1<n_{1}<n_{2}<\cdots<n_{k}<n$, and there is no other factorization $n=m_{1} \cdot m_{2} \cdots \cdot m_{l}$ with $1<m_{1}<m_{2}<\cdots<m_{l}<n$, such that the sequence $m_{1}, m_{2}, \ldots, m_{l}$ is different than the sequence $n_{1}, n_{2}, \ldots, n_{k}$. For example, 6 has the increasing factor property since $6=2 \cdot 3$, and $2<3$, and there are no other factorizations of 6 with strictly increasing factors. 12 does not have this property since it can be factored into strictly increasing factors in two ways, $12=3 \cdot 4$ and $12=2 \cdot 6$. Characterize all positive integers that have the increasing factor property. 3. Find a polynomial $p(x)$ with integer coefficients for which $2 \sqrt{3}+3 \sqrt{2}$ is a root. That is find $p(x)$ such that for some positive integer $n$, and integers $a_{0}, a_{1}, a_{2}, \ldots a_{n}$,

$$
p(x)=a_{0}+a_{1} x+a_{2} x^{2}+\cdots+a_{n} x^{n}, \text { and } p(2 \sqrt{3}+3 \sqrt{2})=0 .
$$

Suppose you are allowed to rearrange the blocks according to the rule that any three blocks that are touching each other can be rearranged as follows. If the three blocks $x, y$, and $z$ all touch each other, then block $x$ can move to the position of block $y$, block $y$ can move to the position of block $z$, and block $z$ can move to the position of block $x$. We call this kind of rearrangement a cycle. For example, in the starting configuration above

$$
\begin{aligned}
& \text { a. Is it possible to obtain } \begin{array}{ll}\underset{C|B| A}{C \mid D} & \text { from } \frac{A \mid B}{C|D| E} \text { using these cycles? Explain. }\end{array} \
& \text { b. Is it possible to obtain } \frac{|B| A}{C|D| E} \text { from } \frac{A|B|}{C|D| E} \text { using these cycles? Explain. }
\end{aligned}
$$

Consider the following game: you are given a sequence of the letters $A, B, C$ and $D$. And you are given the following replacement rules that allow you to replace some combinations of letters with different combinations of letters.

(i) Two distinct adjacent letters among $A, B$ and $C$ can be replaced with the third. More formally, $X Y$ can be replaced with $\mathrm{Z}$ where $X, Y$ and $Z$ are distinct elements of the set ${A, B, C}$. For example, if $X=C, Y=B$ and $Z=A$, this rule allows $C B$ to be replaced with $A$.

(ii) $A B C$ can be replaced with $D$.

(iii) The above rules can be reversed; for example, $C$ can be replaced with $A B$, and $D$ can be replaced by $A B C$.

As an example of a round of play in this game, consider the starting sequence $C B A$. In a first move we can use (iii) in combination with (i) to replace $C$ with $A B$ and get $A B B A$. Then in our next move, we can use (i) to replace $B A$ with $C$ to get $A B C$, which can be replaced by $D$ using (ii) in a third move.

Prove the following:

a. For $X=A, B, C$ or $D, X X$ can be replaced with $D$ in a series of moves.

b. For $X=A, B, C$ or $D$, the pairs $X D$ and $D X$ can each be replaced by $X$ in a series of moves.

c. Show that for any given starting sequence, there is exactly one letter among $A, B, C$ and $D$ that can be reached through a sequence of moves.

$$
\begin{aligned}
& \text { we can cycle A, B and D } \sqrt{C|D| B} \text { to obtain } \frac{D \mid A}{C|B| E} \text {. Then in a second cycle, we can }

\end{aligned}
$$

Consider the following puzzle. You are given a $4 \times 4$ puzzle board:

with four kinds of tiles to be used as puzzle pieces:

The arrows on these tiles point up-left, up-right, down-right and down-left, respectively. For the purposes of this problem, we consider each arrow to point toward a corner as well as toward the two neighboring edges of that corner on the tile. For example, on the first tile above, the arrow is considered to point to the upper-left corner, the left side, and the top side of the tile.

You are given as many tiles of each type as you may need, and the goal of the puzzle is to fill the squares on the board with these tiles according to the following conditions:

(i) Arrows on neighboring tiles (that is, tiles that touch each other on an edge or on a corner) cannot point toward the adjoining (shared) edge or toward the adjoining (shared) corner. For example, the following are not allowed

In (a) and (b) there is a common edge where one arrow points up to that edge and the other arrow points down to that same edge, which is not allowed. In (c) and (d) the arrows point right and left to the same edge, which is not allowed. And in (a), (d) and (e), the two arrows point to the same corner, which is not allowed.

(i) Each row is required to have two tiles with arrows pointing up and two tiles with arrows pointing down, and each column is required to have two tiles with arrows pointing to the left and two tiles with arrows pointing to the right. For example, the following are not allowed

In (a), the first row has all four arrows pointing up and the fourth row has all four arrows pointing down, neither of which are allowed, and in (b), the first column has all arrows pointing left and the fourth column has all arrows pointing right, neither of which are allowed. Does this puzzle have a solution satisfying both conditions (i) and (ii)? If so, how many distinct solutions are possible for this puzzle? Explain carefully how you know the solutions you have accounted for (if any) are the only ones possible.

In this problem we consider sum-two-sequences of numbers; that is, a finite sequence of positive integers that starts with 1 , and where each number that comes later in the sequence is the sum of two previous numbers, including the possibility of adding a number to itself. For example, $1,2,4,8,16$ is a sum-two-sequence, where each number is obtained by adding the previous number to itself. Also, $1,2,3,5,8,13$ is a sum-two-sequence, where after adding 1 to itself, each number is the sum of the two previous. The following is also a sum-two-sequence: $1,2,3,4,5,6$, obtained by starting with 1 and adding 1 to get each successive number

More formally, a sum-two-sequence is a sequence of integers $n_{1}, n_{2}, \ldots, n_{k}$, for $k>0$ such that $n_{1}=$ 1 and for $r=2, \ldots, k$, there are $s, t$ such that. $1 \leq s \leq t<r$. and $n_{r}=n_{s}+n_{t}$. We call $k$ the length of the sum-two-sequence. For each positive integer $N$ we can look for the smallest $k$ such that there is a sum-two-sequence ending in $N$.

For example, we can get $N=10$, in the sequence $1,2,4,8,10$, with $k=5$, and it is not possible to get 10 in a shorter sequence, since the maximum value of $N$ with $k=4$ is 8 .

a. Note that $1,2,4,8,16,32,48,50$ is a sum-two-sequence for $N=50$. Show that 8 is the smallest $k$ for $N=50$ by showing no sum-two-sequence of length 7 ends in 50 .

b. What is the length of the smallest sum-two-sequence for $N=55$ ? In addition to showing that your value of $k$ works for $N=55$, you need to prove there are no smaller values of $k$ that also work for $N=55$.

For the following sudoku-style puzzle, you are given the following 9-by-9 grid,

and you need to fill it in with zeros and ones satisfying the following conditions:

(i) Each row, each column, and each red or blue 3-by-3 box must contain exactly two ones and seven zeros.

(ii) No two ones can be in squares that touch horizontally, vertically, or diagonally.

For example, the following is a solution to this puzzle:

\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \
\hline 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \
\hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \
\hline 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \
\hline 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \
\hline 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \
\hline 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \
\hline 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \
\hline 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \
\hline
\end{tabular}

However, the following is not a solution. Although it satisfies condition (i), the highlighted ones are in squares that touch diagonally, so it does not satisfy condition (ii).

\begin{tabular}{|l|l|l|l|l|l|l|l|l|}
\hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \
\hline 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \
\hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \
\hline 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \
\hline 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \
\hline 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \
\hline 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \
\hline 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \
\hline 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \
\hline
\end{tabular}

a. In the following version of the puzzle, two squares in the center 3-by-3 region have ones on corners across from each other diagonally. Show that it is impossible to fill in the blank squares on this puzzle satisfying conditions (i) and (ii).

b. In the following version of the puzzle there are ones on either end of the middle row of the center $3-$ by-3 region. How many possible solutions are there for completing the blank squares on this puzzle satisfying conditions (i) and (ii)?