Let $n{}$ be a natural number. The playing field for a "Master Sudoku" is composed of the $n(n+1)/2$ cells located on or below the main diagonal of an $n\times n$ square. A teacher secretly selects $n{}$ cells of the playing field and tells his student
[list]
[*]the number of selected cells on each row, and
[*]that there is one selected cell on each column.
[/list]The teacher's selected cells form a Master Sudoku if his student can determine them with the given information. How many Master Sudokus are there?

[i]Proposed by T. Amdeberkhan, M. Ruby and F. Petrov[/i]
To solve the problem, we need to determine the number of Master Sudokus for a given \( n \). Let's break down the solution step by step.

1. **Understanding the Problem:**
   - We have an \( n \times n \) grid.
   - The playing field consists of the cells on or below the main diagonal, which totals \( \frac{n(n+1)}{2} \) cells.
   - The teacher selects \( n \) cells such that:
     - There is exactly one selected cell in each column.
     - The number of selected cells in each row is given.

2. **Defining the Function \( f(n) \):**
   - Let \( f(n) \) be the number of Master Sudokus for a given \( n \).

3. **Base Case:**
   - For \( n = 1 \), there is only one cell, and it must be selected. Thus, \( f(1) = 1 \).

4. **Recursive Step:**
   - Consider the cell selected in the \( n \)-th column. Let it be in the \( k \)-th row.
   - If we remove the \( n \)-th column and the \( k \)-th row, we are left with an \((n-1) \times (n-1)\) grid.
   - The problem reduces to finding the number of Master Sudokus for this \((n-1) \times (n-1)\) grid.
   - The key insight is that the number of Master Sudokus for the \((n-1) \times (n-1)\) grid depends on the number of ways to select the cells in the remaining columns and rows.

5. **Recursive Formula:**
   - The number of ways to select the cells in the remaining columns and rows is given by the sum of the number of ways to select the cells in the smaller grids.
   - Therefore, we have:
     \[
     f(n) = f(n-1) + f(n-2) + \cdots + f(1) + 1
     \]
   - The \( +1 \) accounts for the case where the selected cell in the \( n \)-th column is in the \( n \)-th row.

6. **Inductive Proof:**
   - We need to prove that \( f(n) = 2^{n-1} \) by induction.
   - **Base Case:** For \( n = 1 \), \( f(1) = 1 = 2^{1-1} \).
   - **Inductive Step:** Assume \( f(k) = 2^{k-1} \) for all \( k < n \).
     \[
     f(n) = f(n-1) + f(n-2) + \cdots + f(1) + 1
     \]
     Using the inductive hypothesis:
     \[
     f(n) = 2^{n-2} + 2^{n-3} + \cdots + 2^0 + 1
     \]
     This is a geometric series with the sum:
     \[
     f(n) = 2^{n-1} - 1 + 1 = 2^{n-1}
     \]
   - Thus, by induction, \( f(n) = 2^{n-1} \).

\(\blacksquare\)

The final answer is \( \boxed{ 2^{n-1} } \).