Archive

Posts Tagged ‘trick’

Missing digit – short puzzle

April 15, 2017 Leave a comment

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

Mathematical Mind-Benders, Peter Winkler

Read more…

Advertisements

Project Euler Problem 285

March 25, 2017 Leave a comment

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.

pb285_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…

pb285_1

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

December 11, 2016 Leave a comment

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…

Read more…

Monotonic bijection from naturals to pairs of natural numbers

October 23, 2014 Leave a comment

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

October 8, 2014 Leave a comment

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.

Read more…

Nice inequality similar to IMO 2011

November 23, 2012 Leave a comment

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.

Read more…

Categories: Inequalities, Olympiad Tags: ,

Sleek proof that the harmonic series diverges

April 14, 2012 7 comments

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]}.

Read more…

%d bloggers like this: