Wednesday, April 27, 2011

Floor And Ceiling

Show that there are positive integers $a,b,c,d$ with $b,d < 100$ such that:

$$\lfloor \frac{a}{b} k \rfloor = \lfloor \frac{73}{100} k \rfloor$$

and

$$\lceil \frac{c}{d} k \rceil = \lceil \frac{73}{100} k \rceil$$

For all $k = 1,2,\dots,99$

Note: $\lfloor x \rfloor$ denotes the floor function and $\lceil x \rceil$ denotes the ceiling function

Thursday, April 21, 2011

Shuffling Card

A deck of 31 cards is being shuffled, where at each point, the shuffler may perform the following operation:

1. Cut the deck in half and interleave each half to perform a new deck. The cards at position 1,2,3,...,15 now occupy position 2,4,6,...,30, and the cards at position 16,..., 31 now occupy position 1,3,...,31.

2. Similar to operation one, but with different "cut." The cards at position 1,2,3,...,16 now occupy position 1,3,5,...,31, and the cards at position 17,...,31 now occupy position 2,4,6,...,30.

3. Take $m$ cards from the top and move them to the bottom of the deck (a standard cut).

Starting from the original configuration, how many different configurations can be achieved by repeating the three operations above?

Solution

There are $5.31 = 155$ different configurations.
First, it's clear that the deck can be "rotated" in any amount along one direction, so we only consider rotational configurations.
Step 1 moves cards from position $m$ to $2m \mod 31$
Step 2 moves cards from position $m$ to $2m-1 \mod 31$
Step 3 moves cards from position $m$ to $m+k \mod 31$ for some $k$.

Now, step 3 does not change the rotational configurations. Step 1 and 2 both can be consolidated into the move from $m$ to $2m \mod 31$ and followed by a suitable number of step 3.

Thus, the number of different rotational configurations are the smallest number $n$ such that $2^n \equiv 1 \mod 31$, and that means $n=5$.

So there are 5 rotational configurations and 31 configurations within each rotational configuration, for a total of 155.

Friday, April 8, 2011

Functional Equation

Find all functions $f:N \to N$ such that:

$$f(f(m+n)) = f(m) + f(n) \forall m,n \in N$$

Wednesday, April 6, 2011

Function Composition

Are there real-valued continuous functions $f,g$ defined on real numbers such that
$$f(g(x)) = x^{2011}$$
and
$$g(f(x)) = 2011x$$

for all $x$?

Solution

Applying $g$ to both sides, we have:
$$g(f(g(x))) = g(x^{2011})$$
$$2011g(x) = g(x^{2011})$$

Let $x = 1$, we have $g(1) = 0$

Let $P(y) = g(e^y)$ defined on all $y$ real numbers.
So $P(2011y) = g(e^{2011y}) = g((e^y)^{2011}) = 2011g(e^y) = 2011P(y)$
We conjecture that $P(y) = ay$ for some $a$. Setting $x = e^y$, we have:
$$g(x) = g(e^y) = P(y) = ay = a \log x$$

Now plugging back in, our second equation becomes:
$$a \log f(x) = 2011 x$$
$$f(x) = e^{2011x / a}$$

Testing for compatibility with first equation:

$$f(g(x)) = e^{2011 a \log x / a} = e^{2011 \log x} = x^{2011}$$

Tuesday, April 5, 2011

Symmetric Function in 3 Variables

A function $f$ is defined from a triplet of positive reals to a positive real number $f:R_+^3 \to R_+$ and satisfies the following:

1. $f$ is symmetric in all 3 variables. That is $f(a,b,c) = f(b,a,c) = f(a,c,b) = ...$
2. For any positive real $t$, $f(ta,tb,tc) = tf(a,b,c)$
3. $f(1/a, 1/b, 1/c) = 2011^2/f(a,b,c)$
4. $f(a,b,c) = f(\sqrt{ab}, \sqrt{ab}, c)$

Determine how many triplet of positive integers $(x,y,z)$ are there such that $f(1/x,1/y,1/z) = 1$

Solution

From rule 3, we have $f(1,1,1) = 2011^2/f(1,1,1)$, so $f(1,1,1) = 2011$.

Now, for any $u,v > 0$,
$f(u,v,1/(uv)) = f(\sqrt{uv}, \sqrt{uv}, 1/(uv))$ using rule 4
and
$f(uv,1,1/(uv)) = f(\sqrt{uv}, \sqrt{uv}, 1/(uv))$ using rule 4
So
$f(u,v,1/(uv)) = f(uv,1,1/(uv)) = f(uv, 1/(uv), 1) = f(1,1,1) = 2011$

Now, for any $t,u,v$, let $k = \sqrt[3]{tuv}$, then $t = k^3/uv$
$f(t,u,v) = f(k^3/uv, u, v) = kf(k^2/uv, u/k, v/k) = kf(u/k, v/k, 1/((u/k)(v/k))) = 2011k = 2011\sqrt[3]{tuv}$

Thus $f(t,u,v) = 2011\sqrt[3]{tuv}$ for all $t,u,v$.

Now we need to determine the number of positive integer triples $(x,y,z)$ such that
$$f(1/x,1/y,1/z) = \frac{2011}{\sqrt[3]{xyz}} = 1$$
$$xyz = 2011^3$$
Since 2011 is a prime, there are only the following possibilities:
1. $(1,1,2011^3)$ and all its permutations, there are three triplets.
2. $(1,2011, 2011^2)$ and all its permutations, there are six triplets.
3. $(2011,2011,2011)$, there is one triplet.

So in total, there are ten triplets that satisfy the condition.

The above conditions could be tailored to fit any symmetric functions. For example, for $f = a^2 + b^2 + c^2 + k$ one can have the following conditions:

1. $f$ is symmetric
2. $f(\sqrt{a^2+t},b,c) = f(a,b,c) + t$
3. Any condition that would determine $f(0,0,0)$
4. $f(a,b,c) = f(\sqrt{(a^2+b^2)/2},\sqrt{(a^2+b^2)/2},c)$

Likewise, for $f = ab+bc+ca$ one can have the following conditions (really hard):
1. $f$ is symmetric
2. $f(a+t,b,c) = f(a,b,c) + t(b+c)$
3. Any condition that would determine $f(0,0,0)$
4. $f(a,b,c) = f(k,k,c)$ where $k = \sqrt{(a+c)(b+c)}-c$