Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2021 USAMO Problems/Problem 3"

(→‎Made-up USAMO problem -- (3) is unsolved...)
 
(list)
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
−
A perfect number is a positive integer that is equal to the sum of its proper divisors, such as 6, 28, 496, and 8128. Prove that
+
Let <math>n \geq 2</math> be an integer. An <math>n \times n</math> board is initially empty. Each minute, you may perform one of three moves:
−
(1) All even perfect numbers follow the format <math>\frac{1}{2}M(M+1)</math>, where <math>M</math> is a Mersenne prime;
+
*If there is an L-shaped tromino region of three cells without stones on the board (see figure; rotations not allowed), you may place a stone in each of those cells.
−
(2) All <math>\frac{1}{2}M*(M+1)</math>, where <math>M</math> is a Mersenne prime, are even perfect numbers;
+
*If all cells in a column have a stone, you may remove all stones from that column.
−
(3) There are no odd perfect numbers.
+
*If all cells in a row have a stone, you may remove all stones from that row.
−
 
+
<asy>
−
Note: a Mersenne prime is a prime in the form of <math>2^p-1</math>.
+
unitsize(20);
 +
draw((0,0)--(4,0)--(4,4)--(0,4)--(0,0));
 +
fill((0.2,3.8)--(1.8,3.8)--(1.8, 1.8)--(3.8, 1.8)--(3.8, 0.2)--(0.2, 0.2)--cycle, grey);
 +
draw((0.2,3.8)--(1.8,3.8)--(1.8, 1.8)--(3.8, 1.8)--(3.8, 0.2)--(0.2, 0.2)--(0.2, 3.8), linewidth(2));
 +
draw((0,2)--(4,2));
 +
draw((2,4)--(2,0));
 +
</asy>
 +
For which <math>n</math> is it possible that, after some non-zero number of moves, the board has no stones?
 +
== Solution (WIP) ==

Latest revision as of 12:42, 25 December 2023

Let $n \geq 2$ be an integer. An $n \times n$ board is initially empty. Each minute, you may perform one of three moves:

  • If there is an L-shaped tromino region of three cells without stones on the board (see figure; rotations not allowed), you may place a stone in each of those cells.
  • If all cells in a column have a stone, you may remove all stones from that column.
  • If all cells in a row have a stone, you may remove all stones from that row.

[asy] unitsize(20); draw((0,0)--(4,0)--(4,4)--(0,4)--(0,0)); fill((0.2,3.8)--(1.8,3.8)--(1.8, 1.8)--(3.8, 1.8)--(3.8, 0.2)--(0.2, 0.2)--cycle, grey); draw((0.2,3.8)--(1.8,3.8)--(1.8, 1.8)--(3.8, 1.8)--(3.8, 0.2)--(0.2, 0.2)--(0.2, 3.8), linewidth(2)); draw((0,2)--(4,2)); draw((2,4)--(2,0)); [/asy] For which $n$ is it possible that, after some non-zero number of moves, the board has no stones?

Solution (WIP)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_USAMO_Problems/Problem_3&oldid=208380"