Archive

Posts Tagged ‘trick’

Missing digit – short puzzle

The number $2^{29}$ has $9$ digits, all different; which digit is missing?

Mathematical Mind-Benders, Peter Winkler

Project Euler Problem 285

Another quite nice problem from Project Euler is number 285. The result of the problem depends on the computation of a certain probability, which in turn is related to the computation of a certain area. Below is an illustration of the computation for k equal to 10.

To save you some time, here’s a picture of the case k=1 which I ignored and spent quite a lot of time debugging… Plus, it only affects the last three digits or so after the decimal point…

Here’s a Matlab code which can construct the pictures above and can compute the result for low cases. To solve the problem, you should compute explicitly all these areas.


function problem285(k)

N = 100000;

a = rand(1,N);
b = rand(1,N);

ind = find(abs(sqrt((k*a+1).^2+(k*b+1).^2)-k)<0.5);

plot(a(ind),b(ind),'.');
axis equal

M = k;
pl = 1;

for k=1:M
if mod(k,100)==0
k
end
r1 = (k+0.5)/k;
r2 = (k-0.5)/k;

f1 = @(x) (x<=(-1/k+r1)).*(x>=(-1/k-r1)).*(sqrt(r1^2-(x+1/k).^2)-1/k).*(x>=0).*(x<=1); f1 = @(x) f1(x).*(f1(x)>=0);
f2 = @(x) (x<=(-1/k+r2)).*(x>=(-1/k-r2)).*(sqrt(r2^2-(x+1/k).^2)-1/k).*(x>=0).*(x<=1); f2 = @(x) f2(x).*(f2(x)>=0);

if k == pl
thetas = linspace(0,pi/2,200);
hold on
plot(-1/k+r1*cos(thetas),-1/k+r1*sin(thetas),'r','LineWidth',2);
plot(-1/k+r2*cos(thetas),-1/k+r2*sin(thetas),'r','LineWidth',2);
plot([0 1 1 0 0],[0 0 1 1 0],'k','LineWidth',3);
hold off
axis off
end

A(k) = integral(@(x) f1(x)-f2(x),0,1);

end

xs = xlim;
ys = ylim;

w = 0.01;
axis([xs(1)-w xs(2)+w ys(1)-w ys(2)+w]);

sum((1:k).*A)



Some of the easy Putnam 2016 Problems

Here are a few of the problems of the Putnam 2016 contest. I choose to only list problems which I managed to solve. Most of them are pretty straightforward, so maybe the solutions posted here may be very similar to the official ones. You can find a complete list of the problems on other sites, for example here.

A1. Find the smallest integer ${j}$ such that for every polynomial ${p}$ with integer coefficients and every integer ${k}$, the number

$\displaystyle p^{(j)}(k),$

that is the ${j}$-th derivative of ${p}$ evaluated at ${k}$, is divisible by ${2016}$.

Hints. Successive derivatives give rise to terms containing products of consecutive numbers. The product of ${j}$ consecutive numbers is divisible by ${j!}$. Find the smallest number such that ${2016 | j!}$. Prove that ${j-1}$ does not work by choosing ${p = x^{j-1}}$. Prove that ${j}$ works by working only on monomials…

Monotonic bijection from naturals to pairs of natural numbers

This is a cute problem I found this evening.

Suppose ${\phi : \Bbb{N}^* \rightarrow \Bbb{N}^*\times \Bbb{N}^*}$ is a bijection such that if ${\phi(k) = (i,j),\ \phi(k')=(i',j')}$ and ${k \leq k'}$, then ${ij \leq i'j'}$.

Prove that if ${k = \phi(i,j)}$ then ${k \geq ij}$.

Proof: The trick is to divide the pairs of positive integers into families with the same product.

$\displaystyle \begin{matrix} (1,1) & (1,2) & (1,3) & (1,4) & (1,5) & (1,6) & \cdots \\ & (2,1) & (3,1) & (2,2) & (5,1) & (2,3) & \cdots \\ & & &( 4,1) & & (3,2) & \cdots \\ & & & & & (6,1) & \cdots \end{matrix}$

Note that the ${M}$-th column contains as many elements as the number of divisors of ${M}$. Now we just just use a simple observation. Let ${\phi(k)=(i,j)}$ be on the ${M}$-th column (i.e. ${ij = M}$). If ${n \geq 1}$ then ${\phi(k+n)=(i',j')}$ cannot be on one of the first ${M-1}$ columns. Indeed, the monotonicity property implies ${M = ij \leq i'j'}$. The fact that ${\phi}$ is a bijection assures us that ${\phi(1),...,\phi(k)}$ cover the first ${M-1}$ columns. Moreover, one element from the ${M}$-th column is surely covered, namely ${(i,j) = \phi(k)}$. This means that

$\displaystyle k \geq d(1)+...+d(M-1)+1 \geq M = ij,$

where we have denoted by ${d(n)}$ the number of positive divisors of ${n}$.

Necessary condition for the uniform convergence of a certain series

Let ${a_n}$ be a decreasing sequence of positive numbers such that the series

$\displaystyle \sum_{n = 1}^\infty a_n \sin(nx)$

is uniformly convergent. Then ${(a_n)}$ must satisfy ${(na_n) \rightarrow 0}$.

Note that this result implies that the series ${\sum_{n=1}^\infty a_n \sin(nx)}$ is not uniformly convergent on ${\Bbb{R}}$. It is surprisngly similar to the following result:

Suppose that ${(a_n)}$ is a decreasing sequence of positive real numbers such that the series ${\sum_{n=1}^\infty a_n}$ is convergence. Then ${(na_n) \rightarrow 0}$. It is no surprise that the proofs of these two results are similar.

Nice inequality similar to IMO 2011

Prove that

$(a+b+c)^2 \geq \sum \sqrt{a^4+8a^2bc}$

Note the similarity to the IMO 2011 inequality, and surprisingly the same method works.

Suppose that the harmonic series does converge. Then the sequence of integrable functions functions $f_n : \Bbb{R}_+ \to \Bbb{R}_+,\ f_n=\frac{1}{n} \chi_{[0,n]}$ is bounded above by an integrable function $g: \Bbb{R}_+ \to \Bbb{R}_+,\displaystyle \ g=\sum_{i=1}^\infty \frac{1}{i} \chi_{[i-1,i]}$.