Removing perfect squares

Apparently this is from topcoder, but I believe there must be a more original source for this.

You start with $n$ cards numbered $1,2, \dots n$ placed in order along a line.

Now you make a pass through the cards and remove any that have a perfect square on them. Then you renumber the cards as $1,2 \dots K$ (making sure to maintain the ordering) and keep doing the process of removal and renumbering till there is only one card left.

What was the original number of that card? Can you give a formula in terms of $n$?

Surprising but easy

If

$$\frac{a}{b+c} + \frac{b}{c+a} + \frac{c}{a+b} = 1 $$

Show that

$$\frac{a^2}{b+c} + \frac{b^2}{c+a} + \frac{c^2}{a+b} = 0 $$

Solution [Click here to expand/collapse]

Consider $$a + b + c = (a+b+c)\left(\frac{a}{b+c} + \frac{b}{c+a} + \frac{c}{a+b}\right)$$
This is the same as $$ a + b + c + \frac{a^2}{b+c} + \frac{b^2}{c+a} + \frac{c^2}{a+b}$$
And thus $$ \frac{a^2}{b+c} + \frac{b^2}{c+a} + \frac{c^2}{a+b} = 0$$

A problem from the Vietnam School System

This is a problem given in an exam for middle-schoolers going to high school in Vietnam. It is not easy though.

Given that $a \ge 1, b \ge 1, c \ge$ and $$ab + bc + ac = K$$ where $K$ is a constant $\ge 3$, find with proof, the maximum value of $$a^2 + b^2 + c^2$$

Find $\tan x$

If $$a \cos x + b \sin x = c$$

Find the possible values of $\tan x$ in terms of $a, b, c$.

No calculus IVT for quadratic.

Suppose $$f(x) = x^2 + bx + c$$ and that $f(0) \lt 0$ and $f(1) \gt 0$.

Since $f$ is continuous, by the intermediate value theorem there is some $c \in (0,1)$ such that $f(c) = 0$.

The question here is to prove that in an elementary way, without using any calculus concepts.

Finding the prisoners' names

This is yet another of those crazy warden and mathematical prisoner puzzles.

This time, there are $2n$ prisoners (each with a distinct name).

The warden has a room with $2n$ boxes, each box has the name of exactly one prisoner, and each prisoner's name appears in some box (picked randomly by the warden).

The game the warden plays is that each prisoner goes independently (one by one) in a room and points at some $n$ of the boxes. The goal being that each prisoner should choose the box which contains their own name. If any one of the prisoners does not then they all lose the game. The prisoners aren't allowed to communicate in any way (with each other) what boxes they picked.

If each prisoner picked $n$ boxes at random, then the probability that they win the game (each picks their own name) is $\dfrac{1}{2^n}$ which is pretty small.

They are allowed to choose a strategy before any of them enter the room.

Show that there is a constant $c \gt 0$ (independent of $n$) and a strategy such that the prisoners win the game with probability at least $c$.

Limit of iterated x + 1/x

Suppose $x_1 = 1$ and

$$x_{n+1} = x_n + \frac{1}{x_n}$$

Find

$$\lim_{n \to \infty} \frac{x_n^2 - 2n}{\log n}$$

Expected number of correct coats

This is a classic:


$N$ people attend a party and deposit their ($N$) coats with the coat keeper.

At the end of the party, everyone is drunk (even the coat keeper). The coat keeper hands out a random coat to anyone who comes to claim a coat. Since the owner of the coats are drunk too, no one notices.

What is the expected number of people that get their correct coat back?

A curious inequality

I first saw this in UW's challenge of the week (if I remember correctly), where they used to post a nice math puzzle every week and give the winners (drawn at random from the correct solutions) a gift certificate to Baskin Robbins.

[That has now been discontinued and I believe the pages also have been taken down.]

Anyway, here is the puzzle.

If $x,y \gt 0$ are real numbers, show that

$$x^y + y^x \gt 1$$

Fibonacci property

Fibonacci numbers are defined as $f_0 = f_1 = 1$ and $f_{n+1} = f_n + f_{n-1}$.

Show that a number $F$ is a fibonacci number if and only if one of $5F^2 \pm 4$ is a perfect square.

Defend 3H in a BAM event

This is a hand from the recent Bothell Memorial day sectional. This is a hand from the BAM (board-a-match) teams event.

BAM N/S	Dummy ♠ AT2 ♥ 654 ♦ KQ83 ♣ 987
		You ♠ Q32 ♥ 932 ♦ JT92 ♣ QJ2

W	N	E	S
			1H
1S	2H	2S	3H
P	P	P

Partner leads AK of club and club to your Q (declarer following). What do you do now?



If partner has DA or a heart trick, we need to shift to a spade now.

What if partner does not have the DA or a heart trick?  Since this is BAM, overtricks are important.

If you shift to a low spade and declarer has Jx of spades, you will get squeezed in the pointed suits for declarers 10th trick!

To cater to that, you must shift to the SQ.

Minimum value of sum of trigonometric functions

What is the minimum value of

$$(\sin x + \cos x + \tan x + \csc x + \sec x + \cot x)^2$$


($x$ is real and takes only those values where the function is well defined.)

An integral with $\frac{1}{\log x}$ [Solution]

The problem was:

Suppose $n$ is a positive integer (though the result below does not really need that).

Show that

$$ \int_{0}^{1} \frac{x^n - 1}{\log x} \text{d}x = \log(n+1)$$

Note that the $\log x$ is the $\log$ to base $e$.

Solution

---

This can be solved by the neat trick of differentiating under the integral sign.


Let

 $$ f(z) = \int_{0}^{1} \frac{x^z - 1}{\log x} \text{d}x$$

Differentiating under the integral sign gives us

 $$ f'(z) = \int_{0}^{1} \frac{d \frac{x^z - 1}{\log x}}{dz} \text{d}x$$

and so

 $$ f'(z) = \int_{0}^{1} \frac{x^z \log x}{\log x} \text{d}x  = \int_{0}^{1} x^z \text{d}x  = \frac{1}{z+1}$$

Thus $f(z) = \log(1 + z)$, since $f(0) = 0$.

[Note: There was some handwaving and the right theorems need to be applied, and right bounds on $z$ need to be assumed etc. That is left to the reader]

Don't cross the streams [Solution]

The problem: http://ruffnsluff.blogspot.com/2017/02/dont-cross-streams.html

$N$ red and $N$ blue 2D points, no three collinear. Show that we can pair them off  (red with blue) such that the line segment don't cross.

Solution

---

This has an elegant existential solution (don't know the source).

Of all the possible pairings, pick the pairing which minimizes the sum of the lengths of line segments. No two line segments of this will cross!

Suppose $A,B,C,D$ are points with $A,B$ red and $C,D$ blue such that $AC$ and $BD$ cross (say at $E$).

In the triangles $BEC$ and $AED$ we have that $BE + EC \gt BC$ and $AE + ED \gt AD$ and so $AC + BD \gt AD + BC$.

Uncrossing will reduce the sum of the lengths of the line segments.

There are also constructive solutions, which lead to $O(n^2\log n)$ time algorithms.