MathDB

degree of f=2^k

Source: ISI 2012 #8

May 13, 2012

functioninvariantalgebra unsolvedalgebracombinatorics

Problem Statement

Let

S = \{1,2,3,\ldots,n\}

. Consider a function

f\colon S\to S

. A subset

D

of

S

is said to be invariant if for all

x\in D

we have

f(x)\in D

. The empty set and

S

are also considered as invariant subsets. By

\deg (f)

we define the number of invariant subsets

D

of

S

for the function

f

.
i) Show that there exists a function

f\colon S\to S

such that

\deg (f)=2

.
ii) Show that for every

1\leq k\leq n

there exists a function

f\colon S\to S

such that

\deg (f)=2^{k}

.

Back to Problems View on AoPS