Problem 1260

1. Define the problem and variables:
Let $n = 2023$ and $t = k_{\max}$ be the required maximum. We need to find the greatest integer $k \leq 2023$ such that whenever Alice colors exactly $k$ numbers of the set $\{1, 2, \dots, 2023\}$ in red, Bob can color some of the remaining uncolored numbers in blue, such that the sum of the red numbers is the same as the sum of the blue numbers.

2. Sum of the set:
The sum of the first $n$ natural numbers is given by:
$$S = \frac{n(n+1)}{2}$$
For $n = 2023$:
$$S = \frac{2023 \cdot 2024}{2} = 2023 \cdot 1012$$

3. Condition for sums:
If Alice colors $t$ highest numbers, their sum should be less than half of the sum of all numbers, which is:
$$\frac{n(n+1)}{4}$$
Otherwise, Bob cannot find a subset of the remaining numbers that sums to the same value. Therefore, we need:
$$t(n-t) + \frac{t(t+1)}{2} \leq \frac{n(n+1)}{4}$$

4. Simplify the inequality:
$$t(n-t) + \frac{t(t+1)}{2} \leq \frac{n(n+1)}{4}$$
$$t^2 - t(2n+1) + \frac{n(n+1)}{2} \geq 0$$

5. Solve the quadratic inequality:
The solutions to the quadratic equation:
$$t^2 - t(2n+1) + \frac{n(n+1)}{2} = 0$$
are given by:
$$t_{1,2} = \frac{(2n+1) \pm \sqrt{(2n+1)^2 - 2n(n+1)}}{2}$$
Simplifying the discriminant:
$$(2n+1)^2 - 2n(n+1) = 4n^2 + 4n + 1 - 2n^2 - 2n = 2n^2 + 2n + 1$$
Thus:
$$t_{1,2} = \frac{(2n+1) \pm \sqrt{2n^2 + 2n + 1}}{2}$$

6. **Determine the valid range for $t$:**
Since $t \leq n$, we consider the smaller root:
$$t \leq \frac{(2n+1) - \sqrt{2n^2 + 2n + 1}}{2}$$
Let:
$$t_0 = \left\lfloor \frac{(2n+1) - \sqrt{2n^2 + 2n + 1}}{2} \right\rfloor$$

7. **Verify the maximum $t_0$:**
We need to show that $t_0$ is the required maximum. We assume Alice chooses $t_0$ numbers with sum $s$. Bob needs to find some remaining numbers with sum $s$ or $\frac{n(n+1)}{2} - 2s$.

8. Bob's strategy:
Bob can write $s_0 = a(n+1) + b$ where $0 \leq b \leq n$. If $a \geq 1$, Bob searches for pairs of numbers summing to $b$ or $n+1+b$ and colors them in blue. He then searches for pairs summing to $n+1$ and colors them in blue.

9. Conclusion:
By verifying the conditions and strategies, we find that the maximum $t$ satisfying the conditions is:
$$t_0 = \left\lfloor \frac{(2 \cdot 2023 + 1) - \sqrt{2 \cdot 2023^2 + 2 \cdot 2023 + 1}}{2} \right\rfloor$$

The final answer is $\boxed{673}$.