Let be given integers k and n such that 1<=k<=n. Find the number of ordered k-tuples (a_1,a_2,...,a_n), where a_1, a_2, ..., a_k are different and in the set {1,2,...,n}, satisfying
1) There exist s, t such that 1<=s<t<=k and a_s>a_t.
2) There exists s such that 1<=s<=k and a_s is not congruent to s mod 2.

P.S. This is the only problem from VMO 1996 I cannot find a solution or I cannot solve. But I'm not good at all in combinatoric...
1. **Define the sets and the problem constraints:**
   - Let \( A \) be the set of all ordered \( k \)-tuples \((a_1, a_2, \dots, a_k)\) where \( a_i \in \{1, 2, \dots, n\} \) and \( 1 \leq k \leq n \).
   - Let \( A_1 \) be the set of all ordered \( k \)-tuples satisfying either condition (1) or condition (2) of the problem.
   - Let \( A_2 \) be the set of all ordered \( k \)-tuples \((a_1, a_2, \dots, a_k)\) such that \( a_i < a_{i+1} \) for \( i = 1, 2, \dots, k-1 \) and \( a_i \equiv i \pmod{2} \) for \( i = 1, 2, \dots, k \).

2. **Establish the relationship between the sets:**
   - It is clear that \( A_2 \subset A \) and \( A_1 = A \setminus A_2 \).
   - Therefore, \( |A_1| = |A| - |A_2| \).

3. **Calculate the size of set \( A \):**
   - The total number of ordered \( k \)-tuples \((a_1, a_2, \dots, a_k)\) where \( a_i \in \{1, 2, \dots, n\} \) is given by the number of permutations of \( n \) elements taken \( k \) at a time:
     \[
     |A| = \frac{n!}{(n-k)!}
     \]

4. **Analyze the set \( A_2 \):**
   - For each \((a_1, a_2, \dots, a_k) \in A_2\), we have \( a_i + i \neq a_j + j \) for all \( i \neq j \in \{1, 2, \dots, k\} \).
   - Additionally, \( a_i + i \) is even and \( a_i + i \in \{1, 2, \dots, n+k\} \) for \( i = 1, 2, \dots, k \).

5. **Define the set \( B \):**
   - Let \( B = \{(b_1, b_2, \dots, b_k) \mid b_i \in \{2, 4, \dots, n+k\}, b_i \text{ is even}, b_i < b_{i+1} \text{ for } i = 1, 2, \dots, k-1\} \).

6. **Construct a bijection between \( A_2 \) and \( B \):**
   - Consider the mapping \( f \) from \( A_2 \) to \( B \) defined by \( f(a_1, a_2, \dots, a_k) = (a_1 + 1, a_2 + 2, \dots, a_k + k) \).
   - This mapping is injective because if \( f(a_1, a_2, \dots, a_k) = f(a_1', a_2', \dots, a_k') \), then \( a_i + i = a_i' + i \) implies \( a_i = a_i' \) for all \( i \).

7. **Prove the bijection:**
   - For any \((b_1, b_2, \dots, b_k) \in B\), since \( b_i \) is even and \( b_i \in \{2, 4, \dots, n+k\} \), we have \( 1 \leq b_i - i < b_{i+1} - (i+1) \leq n \) and \( b_i - i \equiv i \pmod{2} \) for all \( i = 1, 2, \dots, k \).
   - Therefore, \((b_1 - 1, b_2 - 2, \dots, b_k - k) \in A_2\).
   - The image of \((b_1 - 1, b_2 - 2, \dots, b_k - k)\) through \( f \) is \((b_1, b_2, \dots, b_k)\), proving that \( f \) is a bijection.

8. **Calculate the size of set \( B \):**
   - The number of ways to choose \( k \) even numbers from \(\{2, 4, \dots, n+k\}\) is given by the binomial coefficient:
     \[
     |B| = \binom{\left\lfloor \frac{n+k}{2} \right\rfloor}{k}
     \]

9. **Combine the results:**
   - Since \( f \) is a bijection, \( |A_2| = |B| \).
   - Therefore, \( |A_1| = |A| - |A_2| = \frac{n!}{(n-k)!} - \binom{\left\lfloor \frac{n+k}{2} \right\rfloor}{k} \).

The final answer is \( \boxed{\frac{n!}{(n-k)!} - \binom{\left\lfloor \frac{n+k}{2} \right\rfloor}{k}} \).