MathDB

Show that there exists a function

Source: Turkish TST 2011 Problem 3

7/23/2011

Let

A

and

B

be sets with

2011^2

and

2010

elements, respectively. Show that there is a function

f:A \times A \to B

satisfying the condition

f(x,y)=f(y,x)

for all

(x,y) \in A \times A

such that for every function

g:A \to B

there exists

(a_1,a_2) \in A \times A

with

g(a_1)=f(a_1,a_2)=g(a_2)

and

a_1 \neq a_2.

functionpigeonhole principlecombinatorics proposedcombinatorics

Binary representations and sum of the digits

Source: Turkish TST 2011 Problem 6

7/23/2011

Let

t(n)

be the sum of the digits in the binary representation of a positive integer

n,

and let

k \geq 2

be an integer.
a. Show that there exists a sequence

(a_i)_{i=1}^{\infty}

of integers such that

a_m \geq 3

is an odd integer and

t(a_1a_2 \cdots a_m)=k

for all

m \geq 1.

b. Show that there is an integer

N

such that

t(3 \cdot 5 \cdots (2m+1))>k

for all integers

m \geq N.

floor functionlimitnumber theorygreatest common divisorinductionprime factorizationnumber theory proposed

Determine the number of functions

Source: Turkish TST 2011 Problem 9

7/23/2011

Let

p

be a prime,

n

be a positive integer, and let

\mathbb{Z}_{p^n}

denote the set of congruence classes modulo

p^n.

Determine the number of functions

f: \mathbb{Z}_{p^n} \to \mathbb{Z}_{p^n}

satisfying the condition

f(a)+f(b) \equiv f(a+b+pab) \pmod{p^n}

for all

a,b \in \mathbb{Z}_{p^n}.

functionmodular arithmeticinductionnumber theory proposednumber theory

3