Existence of functions on finite sets with specific propertise

Question

Let $\Omega$ be an universal set and $|\Omega|=N$, denote $\mathcal{F}$ to be the family of all subsets $\subset \Omega$ with cardinal $n$. We now define a function $f:\mathcal{F}\rightarrow \Omega$, and which satisfies the following properties:

1. $\forall A\in \mathcal{F},\ f(A)\in A$,
2. If $|A_1\cap A_2|=n-1$ then $f(A_1)\not=f(A_2)$.

My question is:

When does this kind of functions exist?

A simple result is that if $n=N-2$ then this kind of functions exist iff $N$ is odd, since we can reduce this question to idempotent symmetric latin square designing problem.

Proof: We change the function to its complement functions, i.e. $f'(\bar{A})=f(A)$. Note that $\bar{A}$ have only two elements, so $f'$ can be regarded as a function $\Omega\times \Omega\rightarrow \Omega$ such that $f'(a,b)\not=a\not=b$ and $f'(a,b)\not=f'(a,c)$ and $f'(a,b)=f'(b,a)$, which is exactly some kind of idempotent symmetric latin square.

We can also show that $n$ should not less then $N/2-1$.

Proof: Suppose not, choosing an arbitrary subset $A'\in \Omega$ and $|A'|=n-2$, since $n<N/2-1$ we can find different $a,b\not\in A'$ and denote $A_1=A'\cup\{a\},\ A_2=A'\cup \{b\}$. For $i=1,2$, we have $N-n+1$ ways to extend $A_i$ to a subset with cardinal $n$ by adding a new element. We claim that there must be an element $e\not\in A_1\cup A_2$, such that $f(A_1\cup\{e\})=f(A_2\cup \{e\})=e$ and which contradict to property 2. But this is easily follows by $2(n+1)<N\Leftrightarrow n<N/2-1$.

So, does anyone know whether this problem can be reduced to any well studied problems?

Actually, I conjecture that this kind of functions do not exist when $n<N-2$, but I don't know how to prove it.

Answer 1

Let $p$ be smallest prime divisor of $n$. I claim that $N<n+p$ though I have no idea about how adequate this estimate is. Consider any subset $C\subset \Omega$ of size $|C|=n+1$. Note that all $n$-element subsets of $C$ have different values of $f$, hence all $n+1$ values are taken each exactly once. Assume that $N\geq n+p$ and choose $U\subset \Omega$, $|U|=n+p$. Consider all $\binom{n+p}{n+1}$ subsets $C\subset U$, $|C|=n+1$, for each of them consider all its subsets $A\subset C$, $|A|=n$. Each element of $C$ equals $f(A)$ for unique $A\subset C$. Sum up by all $C$. Each $A$ is counted $p$ times, while each $a\in U$ appears as $f(A)$ for $\binom{n+p-1}{n}$ subsets, as it lies in $\binom{n+p-1}{n}$ sets $C$. But $\binom{n+p-1}{n}$ is not divisible by $p$, a contradiction.

Answer 2

You do not want $f$ to be injective; so a condition weaker than that for system of distinct representatives should do. If $|\mathcal{F}|=n$ definitely this is true.