Chapter 8.5

Miscellaneous Problems

[41/100%]

Show

LaTeX

Show LaTeX

Section 1Lattice Points in Two and Three Dimensions[13/100%]

Problem 8.238

All three vertices of an equilateral triangle cannot be lattice points.

Problem 8.238.1

A polygon is equiangular, has $n$ sides, and all its vertices are lattice points. Then $n$ is either 4 or 8.

Problem 8.238.1

A polygon is equiangular, has $n$ sides, and all its vertices are lattice points. Then $n$ is either 4 or 8.

Problem 8.238.2

A regular polygon has $n$ sides and all its vertices are lattice points. Then $n=4$ .

Problem 8.238.2

A regular polygon has $n$ sides and all its vertices are lattice points. Then $n=4$ .

Problem 8.239

How thick must the trunks of the trees in a regularly spaced circular forest grow if they are to block completely the view from the center?

Let $s$ be a given positive integer. Let every lattice point $p,q$ that satisfies the inequality $1\leq p^2+q^2\leq s^2$ be the center of a circle of radius $r$ . If $r$ is sufficiently small, there exist rays running from the point 0, 0 to infinity without meeting the circles described above (the forest is transparent); such rays no longer exist if $r$ is sufficiently large (for $r=\tfrac 12$ the circles touch). Let $r=\rho$ be the value of $r$ which divides the two cases (limit of transparency). Then we have

\frac{1}{\sqrt{s^2+1}} \leq \rho < \frac1s .

Problem 8.240

In the plane draw the widest possible infinite straight ``path'', contained between two parallels and avoiding all the lattice points, that makes an angle equal to $\arctan x$ with the $y$ -axis. Denoting the width of this path by $\varphi (x)$ , determine $f(x)=\varphi (x)\sqrt{1+x^2}$ .

Problem 8.241

Two lattice points $x,y$ and $x',y'$ are termed congruent mod $n$ , if

x\equiv x' \pmod n , \qquad y\equiv y' \pmod n .

Among any $kn^2+1$ distinct lattice points there are always $k+1$ that are congruent mod $n$ .

Problem 8.242

In the plane consider a domain of area (Jordan content) $F$ . It may contain no lattice points, but can always be moved parallel to itself so that $[F]+1$ lattice points lie in it.

Problem 8.243

(1)(2)

The lattice points in the closed first quadrant are enumerable. I.e. there exist functions $f(x,y)$ defined for ordered pairs of non-negative integers $x,y$ that combine the following two properties:

(1)

The values assumed by $f(x,y)$ form the set of numbers $1,2,3,4,5,\ldots$ .

(2)

The function $f(x,y)$ takes different values at distinct points; i.e. if $x,y,x',y'$ are integers, $x\geq 0$ , $y\geq 0$ , $x'\geq 0$ , $y'\geq 0$ , $(x-x')^2+(y-y')^2>0$ , then $f(x,y)\neq f(x',y')$ .

There even exist rational entire functions $f(x,y)$ that enumerate the lattice points, i.e. that have the properties (1) (2). An example is the function

f(x,y) = \tfrac 12(x^2+2xy+y^2+3x+y+2) = \binom {x+y+1}{2}+x+1

and the function arising from it by interchanging $x$ and $y$ [the lattice points are counted successively on the line segments

x+y=0, \quad x+y=1, \quad x+y=2, \quad \ldots , \quad x\geq 0, \quad y\geq 0 .

Let $f(x,y)$ be a rational entire function of degree $m$

f(x,y) = \varphi _0(x,y)+\varphi _1(x,y)+\cdots +\varphi _m(x,y) ,

where $\varphi_\mu (x,y)$ denotes a rational entire homogeneous function of degree $\mu$ . If $f(x,y)$ enumerates the lattice points, then clearly $\varphi_m(x,y)\geq 0$ for $x\geq 0$ , $y\geq 0$ . If $\varphi_m(x,y)>0$ for $x\geq 0$ , $y\geq 0$ , $x+y>0$ and $f(x,y)$ enumerates the lattice points, then the degree of $f(x,y)$ is

m=2 .

[The number of lattice points contained inside the contour line $f(x,y)=\text{const.}$ is related to the enclosed area.]]

Problem 8.244

Consider the square domain $\tfrac 12\leq x\leq n+\tfrac 12$ , $\tfrac 12\leq y\leq n+\tfrac 12$ as a chess board with $n^2$ squares'', i.e. by means of straight lines parallel to the axis divide it into $n^2$ squares of unit area. The problem of the $n$ queens'' requires us to choose from the $n^2$ lattice points that constitute the centers of the $n^2$ squares $n$ lattice points $(x_1,y_1),(x_2,y_2),\ldots ,(x_n,y_n)$ that satisfy the $2n(n-1)$ inequalities

x_\mu \neq x_\nu , \qquad y_\mu \neq y_\nu , \qquad x_\mu -x_\nu \neq y_\mu -y_\nu , \qquad x_\mu -x_\nu \neq -(y_\mu -y_\nu ) ,

where $\mu \neq \nu$ ; $\mu ,\nu =1,2,\ldots ,n$ . Replace the inequalities by the more restrictive ``incongruence relations''

x_\mu \not\equiv x_\nu , \qquad y_\mu \not\equiv y_\nu , \qquad x_\mu -x_\nu \not\equiv y_\mu -y_\nu , \qquad x_\mu -x_\nu \not\equiv -(y_\mu -y_\nu )

$\pmod n$ and show that these have a solution if and only if $n$ is relatively prime to 6.

Problem 8.244.1

A regular polygon has $n$ sides and all its vertices are lattice points. Then $n$ is equal to 3, 4 or 6.

Problem 8.244.1

A regular polygon has $n$ sides and all its vertices are lattice points. Then $n$ is equal to 3, 4 or 6.

Problem 8.244.2

(continued). Give examples showing that the three cases $n=3,4$ and 6 can actually occur.

Problem 8.244.2

(continued). Give examples showing that the three cases $n=3,4$ and 6 can actually occur.

Problem 8.244.3

All the vertices of a regular polyhedron are lattice points. Then the polyhedron is either a cube or a tetrahedron or an octahedron.

Problem 8.244.3

All the vertices of a regular polyhedron are lattice points. Then the polyhedron is either a cube or a tetrahedron or an octahedron.

Problem 8.244.4

(continued). Give examples showing that the three cases mentioned above can actually occur.

Problem 8.244.4

(continued). Give examples showing that the three cases mentioned above can actually occur.

Section 2Miscellaneous Problems[28/100%]

Problem 8.245

Let $q$ denote an odd prime number and let $r_1,r_2,\ldots ,r_q$ and $s_1,s_2,\ldots ,s_q$ be two complete systems of residues mod $q$ . Then the $q$ numbers $r_1s_1,r_2s_2,\ldots ,r_qs_q$ do not form a complete system of residues mod $q$ .

Problem 8.246

Let the highest power of the odd prime number $p$ that divides the number $n$ be $p^\alpha$ , $\alpha \geq 1$ . Then we have

1^\lambda +2^\lambda +3^\lambda +\cdots +n^\lambda \equiv -\frac np \quad \text{or} \quad 0 \pmod{p^\alpha } ,

according as $\lambda$ is or is not divisible by $p-1$ , $\lambda =1,2,3,\ldots$ .

Problem 8.247

Let $p$ be the smallest prime number that divides $n$ . Then there exist two complete systems of residues mod $n$

r_1, \ r_2, \ \ldots , \ r_n , \qquad s_1, \ s_2, \ \ldots , \ s_n

such that each of the $p-2$ lines

r_1+s_1, \ r_2+s_2, \ \ldots , \ r_n+s_n , \qquad r_1+2s_1, \ r_2+2s_2, \ \ldots , \ r_n+2s_n ,

\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots

r_1+(p-2)s_1, \ r_2+(p-2)s_2, \ \ldots , \ r_n+(p-2)s_n

represents a complete system of residues mod $n$ . However then

r_1+(p-1)s_1, \ r_2+(p-1)s_2, \ \ldots , \ r_n+(p-1)s_n

is not a complete system of residues mod $n$ .

Problem 8.247.1

If $p$ is a prime number, then

\binom p1, \quad \binom p2, \quad \binom p3, \quad \ldots , \quad \binom {p}{p-1} ,

s_2^p, \quad s_3^p, \quad \ldots , \quad s_{p-1}^p ,

S_2^p, \quad S_3^p, \quad \ldots , \quad S_{p-1}^p

are divisible by $p$ . (For the definitions of $s_k^n$ and $S_k^n$ see the introductions to Problem 197 and Problem 186 of Part I, respectively.)

Problem 8.247.1

If $p$ is a prime number, then

\binom p1, \quad \binom p2, \quad \binom p3, \quad \ldots , \quad \binom {p}{p-1} ,

s_2^p, \quad s_3^p, \quad \ldots , \quad s_{p-1}^p ,

S_2^p, \quad S_3^p, \quad \ldots , \quad S_{p-1}^p

are divisible by $p$ . (For the definitions of $s_k^n$ and $S_k^n$ see the introductions to Problem 197 and Problem 186 of Part I, respectively.)

Problem 8.247.2

If $p$ is an odd prime, the coefficients of the Tchebychev polynomial $T_p(x)$ (defined at the beginning of Part Six) are all divisible by $p$ , with the exception of the leading coefficient which is equal to $2^{p-1}$ .

Problem 8.247.2

Problem 8.248

Every integral power of a number $n$ can be represented as the sum of $n$ consecutive odd integers.

Problem 8.249

A number in the sequence $2,3,4,\ldots ,n$ ( $n>2$ ) is relatively prime to all the other numbers if and only if it is a prime number that exceeds $n/2$ . (That such a prime number always exists for $n>2$ was proved by Tchebychev. Cf. Oeuvres, Vol. 1, p. 63, St. Petersbourg 1899.)

Problem 8.250

The partial sums of the harmonic series

\frac11+\frac12+\frac13+\cdots +\frac1n

for $n>1$ are not equal to an integer. This follows directly from the Tchebychev theorem [249], but is to be proved without using that theorem.

Problem 8.251

The sum of two or more consecutive terms of the harmonic series, i.e. a sum of the form

\frac1n+\frac{1}{n+1}+\cdots +\frac1m , \qquad n=1,2,3,\ldots ; \quad n<m ,

cannot be an integer. If it is written in the form of a fraction in its lowest terms, then its denominator is even and its numerator is odd.

Problem 8.252

If the positive integer $n$ is divisible by all numbers that are $\leq \sqrt n$ , then $n$ is either 24 or a divisor of 24.

More generally show by an elementary argument the following: If $0<\alpha <1$ , then there exist only a finite number of positive integers $n$ such that $n$ is divisible by $1,2,3,\ldots ,[n^\alpha ]$ .

Problem 8.253

Let $Q$ be a prime number and relatively prime to $10P$ . The arithmetic mean of the digits in a period of the expression of $P/Q$ as a decimal fraction is 4.5 if and only if the length of the period is an even number.

Problem 8.254

The number $n=2^h+1$ , $h\geq 2$ is a prime number if and only if

3^{\frac{n-1}{2}} \equiv -1 \pmod n .

Problem 8.255

The following theorem given by Euler as a conjecture is true: The Diophantine equation

4xyz-x-y-t^2=0

has no solution in positive integers $x,y,z,t$ .

Problem 8.256

If the prime number $q\geq 11$ , then there always exist positive odd prime numbers $p_1,p_2,p_3,p_4$ , not necessarily distinct, that are all smaller than $q$ , and satisfy the equations

\left(\frac{p_1}{q}\right) = +1 , \qquad \left(\frac{p_2}{q}\right) = -1 , \qquad \left(\frac{q}{p_3}\right) = +1 , \qquad \left(\frac{q}{p_4}\right) = -1

respectively. $\left[\left(\dfrac {p_1}{q}\right)\right.$ etc., are Legendre symbols defined in Problem 45 of Part V.]

Problem 8.257

The decimal fraction

0.23571113171923\ldots

(formed by writing consecutively all the prime numbers) is irrational. [249, 110.]

Problem 8.258

The number

e = 1+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\frac{1}{4!}+\cdots

is irrational.

Problem 8.259

The number $e$ is not only irrational, but it is also not an algebraic number of the second degree, i.e. it cannot satisfy an equation of the form

ae+be^{-1}+c=0 ,

where $a,b,c$ are integers and are not all $=0$ .

Problem 8.260

If the Euler (Mascheroni) constant $C=-\Gamma '(1)$ were a rational number, then $\Gamma '(n+1)$ would have to be an integer for all integers $n$ from some point onward.

Problem 8.260.1

The number

\lambda = \frac{\log 3}{\log 2}

is irrational.

Problem 8.260.1

The number

\lambda = \frac{\log 3}{\log 2}

is irrational.

Problem 8.260.2

The numbers $a$ and $b$ are positive; $a$ may be rational or irrational and the same holds for $b$ , and so there are four possible cases. Show by means of examples that $a^b$ can be rational or irrational in each of these four cases (eight examples are required).

Problem 8.260.2

Problem 8.261

The question whether the number $\pi$ has the property that the arithmetic mean of its first $n$ decimal places converges to 4.5 must be left unresolved. If however the number $\pi$ has this property then the number $4-\pi$ has the same property.

Problem 8.262

Denote by $q_n$ the denominator of the $n$ th Bernoulli number $B_n$ [182]. Then we have

\lim _{n\to \infty } \sqrt[n]{\frac{q_1q_2q_3\cdots q_n}{(2n)!}} = \frac12 .

Problem 8.262.1

If $\zeta (s)$ denotes the Riemann zeta-function defined in the introduction to 39,

\lim _{n\to \infty } \left(\zeta (2)+\zeta (3)+\cdots +\zeta (n+1)-n\right) = 1 .

Problem 8.262.1

If $\zeta (s)$ denotes the Riemann zeta-function defined in the introduction to 39,

\lim _{n\to \infty } \left(\zeta (2)+\zeta (3)+\cdots +\zeta (n+1)-n\right) = 1 .

Problem 8.262.2

\lim _{n\to \infty } \left(\frac12\zeta (2)+\frac13\zeta (3)+\cdots +\frac1n\zeta (n)-\log n\right) = 0 .

Problem 8.262.2

\lim _{n\to \infty } \left(\frac12\zeta (2)+\frac13\zeta (3)+\cdots +\frac1n\zeta (n)-\log n\right) = 0 .

Problem 8.263

Let the arithmetic function $f(n)$ be multiplicative [introduction to Chapter 1, § 6] and converge to 0 as $n$ tends to infinity through the prime numbers and the powers of prime numbers. Then $f(n)$ also satisfies the stronger requirement that

\lim _{n\to \infty } f(n) = 0

as $n$ tends to infinity through all positive integers.

Problem 8.264

For every given positive number $\delta$ ,

\lim _{n\to \infty } \frac{n^{1-\delta }}{\varphi (n)} = 0 , \qquad \lim _{n\to \infty } \frac{\tau (n)}{n^\delta } = 0 .

Problem 8.265

Let the quadratic polynomial $ax^2+bx+c$ with integral coefficients be represented by the lattice point $a,b,c$ of a three-dimensional cubic lattice. Let the number of those lattice points that lie in the cube

-n\leq a\leq n , \qquad -n\leq b\leq n , \qquad -n\leq c\leq n

and correspond to a reducible polynomial be $r_n$ . Prove that

\lim _{n\to \infty } \frac{r_n}{(2n+1)^3} = 0 .

(It is in a certain sense the ``normal case'' for a quadratic polynomial to be irreducible.)

Problem 8.266

The probability that a polynomial with integral coefficients of given degree is reducible is equal to 0. More precisely: Let $h$ be an integer, $h\geq 2$ , and let $r_n$ denote the number of those lattice points of $(h+1)$ -dimensional space that lie in the cube

-n\leq a_0\leq n , \qquad -n\leq a_1\leq n , \qquad \ldots , \qquad -n\leq a_h\leq n

and correspond to a reducible polynomial $a_0x^h+a_1x^{h-1}+\cdots +a_h$ . Then we have

r_n = O(n^h\log ^2n) .

(This result generalizes and improves 265.) [Problem 46 of Part II.]