We have your learning goals covered with Spring and Summer courses available. Enroll today!

Contests & Programs AMC and other contests, summer programs, etc.
AMC and other contests, summer programs, etc.
3 M G
BBookmark  VNew Topic kLocked
Contests & Programs AMC and other contests, summer programs, etc.
AMC and other contests, summer programs, etc.
3 M G
BBookmark  VNew Topic kLocked
G
Topic
First Poster
Last Poster
k a March Highlights and 2025 AoPS Online Class Information
jlacosta   0
Mar 2, 2025
March is the month for State MATHCOUNTS competitions! Kudos to everyone who participated in their local chapter competitions and best of luck to all going to State! Join us on March 11th for a Math Jam devoted to our favorite Chapter competition problems! Are you interested in training for MATHCOUNTS? Be sure to check out our AMC 8/MATHCOUNTS Basics and Advanced courses.

Are you ready to level up with Olympiad training? Registration is open with early bird pricing available for our WOOT programs: MathWOOT (Levels 1 and 2), CodeWOOT, PhysicsWOOT, and ChemWOOT. What is WOOT? WOOT stands for Worldwide Online Olympiad Training and is a 7-month high school math Olympiad preparation and testing program that brings together many of the best students from around the world to learn Olympiad problem solving skills. Classes begin in September!

Do you have plans this summer? There are so many options to fit your schedule and goals whether attending a summer camp or taking online classes, it can be a great break from the routine of the school year. Check out our summer courses at AoPS Online, or if you want a math or language arts class that doesn’t have homework, but is an enriching summer experience, our AoPS Virtual Campus summer camps may be just the ticket! We are expanding our locations for our AoPS Academies across the country with 15 locations so far and new campuses opening in Saratoga CA, Johns Creek GA, and the Upper West Side NY. Check out this page for summer camp information.

Be sure to mark your calendars for the following events:
[list][*]March 5th (Wednesday), 4:30pm PT/7:30pm ET, HCSSiM Math Jam 2025. Amber Verser, Assistant Director of the Hampshire College Summer Studies in Mathematics, will host an information session about HCSSiM, a summer program for high school students.
[*]March 6th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar on Math Competitions from elementary through high school. Join us for an enlightening session that demystifies the world of math competitions and helps you make informed decisions about your contest journey.
[*]March 11th (Tuesday), 4:30pm PT/7:30pm ET, 2025 MATHCOUNTS Chapter Discussion MATH JAM. AoPS instructors will discuss some of their favorite problems from the MATHCOUNTS Chapter Competition. All are welcome!
[*]March 13th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar about Summer Camps at the Virtual Campus. Transform your summer into an unforgettable learning adventure! From elementary through high school, we offer dynamic summer camps featuring topics in mathematics, language arts, and competition preparation - all designed to fit your schedule and ignite your passion for learning.[/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Sunday, Mar 2 - Jun 22
Friday, Mar 28 - Jul 18
Sunday, Apr 13 - Aug 10
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21


Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, Mar 23 - Jul 20
Monday, Apr 7 - Jul 28
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Sunday, Mar 16 - Jun 8
Wednesday, Apr 16 - Jul 2
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Sunday, Mar 2 - Jun 22
Wednesday, Apr 16 - Jul 30
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Sunday, Mar 23 - Aug 3
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Friday, Apr 11 - Jun 27
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Sunday, Mar 16 - Aug 24
Wednesday, Apr 9 - Sep 3
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Wednesday, Mar 5 - May 21
Tuesday, Jun 10 - Aug 26

Calculus
Sunday, Mar 30 - Oct 5
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Friday, Apr 11 - Jun 27
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Tuesday, Mar 4 - May 20
Monday, Mar 31 - Jun 23
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Monday, Mar 24 - Jun 16
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Sunday, Mar 30 - Jun 22
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Tuesday, Mar 25 - Sep 2
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Sat & Sun, Apr 26 - Apr 27 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Mar 2, 2025
0 replies
HOT TAKE: MIT SHOULD NOT RELEASE THEIR DECISIONS ON PI DAY
alcumusftwgrind   7
N an hour ago by dragoon
rant lol

Imagine a poor senior waiting for their MIT decisions just to have their hopes CRUSHED on 3/14 and they can't even celebrate pi day...

and even worse, this year's pi day is special because this year is a very special number...

7 replies
alcumusftwgrind
6 hours ago
dragoon
an hour ago
rows are DERANGED and a SOCOURGE to usajmo .
GrantStar   26
N 2 hours ago by joshualiu315
Source: USAJMO 2024/4
Let $n \geq 3$ be an integer. Rowan and Colin play a game on an $n \times n$ grid of squares, where each square is colored either red or blue. Rowan is allowed to permute the rows of the grid and Colin is allowed to permute the columns. A grid coloring is orderly if: [list] [*]no matter how Rowan permutes the rows of the coloring, Colin can then permute the columns to restore the original grid coloring; and [*]no matter how Colin permutes the columns of the coloring, Rowan can then permute the rows to restore the original grid coloring. [/list] In terms of $n$, how many orderly colorings are there?

Proposed by Alec Sun
26 replies
GrantStar
Mar 21, 2024
joshualiu315
2 hours ago
Geo equals ABsurdly proBEMatic
ihatemath123   73
N 2 hours ago by joshualiu315
Source: 2024 USAMO Problem 5, JMO Problem 6
Point $D$ is selected inside acute $\triangle ABC$ so that $\angle DAC = \angle ACB$ and $\angle BDC = 90^{\circ} + \angle BAC$. Point $E$ is chosen on ray $BD$ so that $AE = EC$. Let $M$ be the midpoint of $BC$.

Show that line $AB$ is tangent to the circumcircle of triangle $BEM$.

Proposed by Anton Trygub
73 replies
ihatemath123
Mar 21, 2024
joshualiu315
2 hours ago
average FE
KevinYang2.71   74
N 3 hours ago by joshualiu315
Source: USAJMO 2024/5
Find all functions $f:\mathbb{R}\rightarrow\mathbb{R}$ that satisfy
\[
f(x^2-y)+2yf(x)=f(f(x))+f(y)
\]for all $x,y\in\mathbb{R}$.

Proposed by Carl Schildkraut
74 replies
KevinYang2.71
Mar 21, 2024
joshualiu315
3 hours ago
No more topics!
Tasteful domino tilings
azjps   35
N Jan 1, 2024 by XD012
Source: 2009 USAMO problem 3
We define a chessboard polygon to be a polygon whose sides are situated along lines of the form $ x = a$ or $ y = b$, where $ a$ and $ b$ are integers. These lines divide the interior into unit squares, which are shaded alternately grey and white so that adjacent squares have different colors. To tile a chessboard polygon by dominoes is to exactly cover the polygon by non-overlapping $ 1 \times 2$ rectangles. Finally, a tasteful tiling is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a $ 3 \times 4$ rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.

IMAGE a) Prove that if a chessboard polygon can be tiled by dominoes, then it can be done so tastefully.

b) Prove that such a tasteful tiling is unique.
35 replies
azjps
Apr 30, 2009
XD012
Jan 1, 2024
Tasteful domino tilings
G H J
Source: 2009 USAMO problem 3
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
azjps
1405 posts
#1 • 5 Y
Y by pifinity, AbdulelahAltaf, Adventure10, Mango247, and 1 other user
We define a chessboard polygon to be a polygon whose sides are situated along lines of the form $ x = a$ or $ y = b$, where $ a$ and $ b$ are integers. These lines divide the interior into unit squares, which are shaded alternately grey and white so that adjacent squares have different colors. To tile a chessboard polygon by dominoes is to exactly cover the polygon by non-overlapping $ 1 \times 2$ rectangles. Finally, a tasteful tiling is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a $ 3 \times 4$ rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.

[asy]size(300); pathpen = linewidth(2.5);
void chessboard(int a, int b, pair P){ 
 for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j) 
  if((i+j) % 2 == 1) fill(shift(P.x+i,P.y+j)*unitsquare,rgb(0.6,0.6,0.6)); 
 D(P--P+(a,0)--P+(a,b)--P+(0,b)--cycle);
}
chessboard(2,2,(2.5,0));fill(unitsquare,rgb(0.6,0.6,0.6));fill(shift(1,1)*unitsquare,rgb(0.6,0.6,0.6)); chessboard(4,3,(6,0)); chessboard(4,3,(11,0)); MP("\mathrm{Distasteful\ tilings}",(2.25,3),fontsize(12)); 

/* draw lines */
D((0,0)--(2,0)--(2,2)--(0,2)--cycle); D((1,0)--(1,2)); D((2.5,1)--(4.5,1)); D((7,0)--(7,2)--(6,2)--(10,2)--(9,2)--(9,0)--(9,1)--(7,1)); D((8,2)--(8,3)); D((12,0)--(12,2)--(11,2)--(13,2)); D((13,1)--(15,1)--(14,1)--(14,3)); D((13,0)--(13,3));[/asy] a) Prove that if a chessboard polygon can be tiled by dominoes, then it can be done so tastefully.

b) Prove that such a tasteful tiling is unique.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
chelseafc
18 posts
#2 • 1 Y
Y by Adventure10
only proved a), I think my proof is correct. I proved by doing "move"s(every time you meet a distasteful tiling, you turn the direction of that 4 cells' tiling), after each move, you will get a completely new arrangement of tiling.(For this part, I suppose if an arrangement will appear twice, then let it be the initial arrangement, now I put 1 counter in the 4 cells after each move, which means after some moves all the cells will have an even number of counters in it. Since we never do "move" at the same 4 cells continuously, every time there will be a new cell which the counter turns from 0 to 1. Eventually it will get to the 4 corner cells. But it's obvious that the 4 corner cells can only be moved at most once. Which means there will always be some cells with odd counters in it. Which means no arrangement will appear twice). After each move, the number of distasteful tilings may change or not, but the point is if it never gets to 0, it means it will always be a possible "next move", which means there will be a new arrangement. Since the total arrangement number is limited, the number of distasteful tilings have to get to 0 after some moves.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
krakola45
30 posts
#3 • 2 Y
Y by Adventure10, Mango247
That's what I did, but I said that every 2x2 square cannot be "moved" back to its original position, so if some specific 2x2 square is distasteful, it can never be distasteful again, similarly with any other 2x2 square. So therefore, this process must be finite, and eventually it will become tasteful.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
chelseafc
18 posts
#4 • 1 Y
Y by Adventure10
Had anyone solved part b?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JSteinhardt
947 posts
#5 • 3 Y
Y by Adventure10, Mango247, and 1 other user
This is a bit hard to explain without a picture, but I'll try anyways. Solution by Paul Christiano.

part a

part b
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
kstan013
848 posts
#6 • 2 Y
Y by Adventure10, Mango247
Basically, the only way to tile them tastefully was to start in the middle and layer the other tiles outward, if you know what I mean. I also tried to prove that was the only way by doing

l W G
l G W

and showing that there was no possible way to create a square corner while avoidind distaste. The way to tile them was:

l W G l W G l W G l... (2 rows if needed) in the middle. When you add an outer layer, they are staggered, so there is no possible distaste since there are no 2 x 2 squares.

Kinda hard to explain w/o picture.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
chelseafc
18 posts
#7 • 2 Y
Y by Adventure10, Mango247
The solution seems good. Thanks!

By the way, had Paul Christiano solved every single problem? If so then he may get perfect! wow!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
matt276eagles
1322 posts
#8 • 2 Y
Y by Adventure10, Mango247
Paul was a senior last year. He's at MIT now, so I assume he was just trying the problems for fun.

The solution seems nice, but I don't understand the part about the forced squares and the diagonal.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jmerry
12096 posts
#9 • 12 Y
Y by qbzvavba, rashah76, Adventure10, Mango247, and 8 other users
I have a very neat existence proof:

Choose a number $ r>1$. Assign to the tile with lower left corner at $ (a,b)$ the weight $ (-r)^{a+b}$. Shade the squares with positive weight, noting that they are at locations with $ a+b$ even.

Sum the weights of all tiles, multiplied by $ 1$ for those in horizontal dominos and $ -1$ for those in vertical dominos. A $ 2\times 2$ distasteful block with lower left corner at $ a+b$ contributes $ -r^{a+b}(r-1)^2$, while its tasteful counterpart gives $ r^{a+b}(r-1)^2$.
There are finitely many possible sums, and finitely many tilings, so some tiling has a maximal sum. If this maximum had any distasteful blocks, we could reverse them to increase the sum. This doesn't happen, so the maximum is tasteful tiling.

- JSteinhardt: I'm not at all convinced that that argument handles irregular grids. If that "upper left" tile isn't uppermost, we may be able to escape- in particular, if the tile one spot up and one to the right is in the grid, we can put a vertical tile there. Then that tile might not even be a corner...
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ZzZzZzZzZzZz
431 posts
#10 • 1 Y
Y by Adventure10
Very elegant proof. But does it address part b)?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jmerry
12096 posts
#11 • 2 Y
Y by Adventure10, Mango247
No, it doesn't. The method doesn't rule out two local maxima.

I've been working on part (b); so far I can say a lot about the structure of a minimal counterexample, but I can't rule it out completely. Uniqueness is false if we allow holes in the middle, by the way.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JSteinhardt
947 posts
#12 • 2 Y
Y by Adventure10, Mango247
So I guess I forgot to add in a few lemmas that I thought weren't needed, but now I realize you do. Essentially if there is anything that is adjacent to only one other square then there is only one possible way that you can place a tile to cover that square, so we can rule out all those cases. Then if we consider the top row and go as far left as possible we can safely apply the same argument as before from that square.

EDIT: Nevermind I see your objection, if I do that then my WLOG is no longer appropriate because I've broken symmetry.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jmerry
12096 posts
#13 • 6 Y
Y by Adventure10, Mango247, and 4 other users
I think I've made the breakthrough I needed.
Uniqueness

Those fake pictures were a pain, but it's unreadable without something. Does anyone know a better (longer) horizontal dash symbol in $ \text{\LaTeX}$?

[Added in edit]
krakola45 wrote:
...but I said that every 2x2 square cannot be "moved" back to its original position, so if some specific 2x2 square is distasteful, it can never be distasteful again
Not true. In large polygons, many of the distasteful blocks will return; in a $ 2n\times 2n$ square, it takes $ n+8\binom{n+1}{3}=\frac{n(8n^2+6n-8)}{6}$ moves to go from the worst arrangement (no tasteful $ 2\times 2$ blocks) to the best, or half that from a random tiling to the tasteful tiling on average. The average number of times each $ 2\times 2$ block is moved is proportional to the linear size, and a block in the middle can move twice in something as simple as a $ 4\times 4$ board.

I have a feeling that a lot of people are wrong in subtle ways, and didn't solve as much of this problem as they thought.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Yongyi781
2142 posts
#14 • 2 Y
Y by Adventure10, Mango247
Jmerry, I think you need to be more rigorous on what you mean by "some lower left corner." Some polygons don't have a "lower left corner." Do you mean the square for which $ a+b$ is a minimum?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jmerry
12096 posts
#15 • 2 Y
Y by Adventure10, Mango247
The definition of a lower left corner: any square in the polygon for which neither the square directly below nor the square directly to the left is in the polygon. Every polygon must have at least one, and some polygons have many.
Minimizing $ x+y$ would make the argument simpler, though. In that case, we can't keep going down in case (b).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
probability1.01
2743 posts
#16 • 4 Y
Y by Adventure10, Mango247, and 2 other users
Whoa, looks like you've used a similar approach to my original one, but I was not satisfied with the casework involved.

possible improvement
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jmerry
12096 posts
#17 • 2 Y
Y by Adventure10, Mango247
The first two parts look good. The hamster will get confused when it runs into the middle of a tasteful block- remember, those are really just the same as distasteful blocks except for coloring. That idea also needs an argument that there are no tasteful blocks inside.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
probability1.01
2743 posts
#18 • 2 Y
Y by Adventure10, Mango247
Ahh, but it misses all of those because of how rhythmically it is running. If you set the first step correctly, it should exactly be a question of whether there is a distasteful block obstructing it every time, and there should be no problems.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Yongyi781
2142 posts
#19 • 1 Y
Y by Adventure10
Lol hamsters... if only I had the liberty not only to write a boilerplate proof in the given time but also to add humor to it...
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jmerry
12096 posts
#20 • 1 Y
Y by Adventure10
I see now. The specific fix: go horizontally if the tile to the upper right is shaded, and vertically if it's unshaded. You can enter the middle of a distasteful block that way, but not a tasteful block.
Yongyi781 wrote:
Lol hamsters... if only I had the liberty not only to write a boilerplate proof in the given time but also to add humor to it...
Well, we're not working in real time here. The last time I actually competed in the USAMO was 2000, and I first saw these problems Thursday morning.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mszew
1044 posts
#21 • 2 Y
Y by Adventure10, Mango247
azjps wrote:
We define a chessboard polygon to be a polygon whose sides are situated along lines of the form $ x = a$ or $ y = b$, where $ a$ and $ b$ are integers. These lines divide the interior into unit squares, which are shaded alternately grey and white so that adjacent squares have different colors. To tile a chessboard polygon by dominoes is to exactly cover the polygon by non-overlapping $ 1 \times 2$ rectangles. Finally, a tasteful tiling is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a $ 3 \times 4$ rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.

[asy]size(100); pathpen = linewidth(2.5);
void chessboard(int a, int b, pair P){ 
 for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j) 
  if((i+j) % 2 == 1) fill(shift(P.x+i,P.y+j)*unitsquare,rgb(0.6,0.6,0.6)); 
 D(P--P+(a,0)--P+(a,b)--P+(0,b)--cycle);
}
chessboard(2,2,(2.5,0));fill(unitsquare,rgb(0.6,0.6,0.6));fill(shift(1,1)*unitsquare,rgb(0.6,0.6,0.6)); chessboard(4,3,(6,0)); chessboard(4,3,(11,0)); MP("\mathrm{Distasteful\ tilings}",(2.25,3),fontsize(12)); 

/* draw lines */
D((0,0)--(2,0)--(2,2)--(0,2)--cycle); D((1,0)--(1,2)); D((2.5,1)--(4.5,1)); D((7,0)--(7,2)--(6,2)--(10,2)--(9,2)--(9,0)--(9,1)--(7,1)); D((8,2)--(8,3)); D((12,0)--(12,2)--(11,2)--(13,2)); D((13,1)--(15,1)--(14,1)--(14,3)); D((13,0)--(13,3));[/asy] a) Prove that if a chessboard polygon can be tiled by dominoes, then it can be done so tastefully.

b) Prove that such a tasteful tiling is unique.

Can any chessboard polygon with even size bigger or equal to 4 be tiled uniquely tastefully?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jmerry
12096 posts
#22 • 2 Y
Y by Adventure10, Mango247
A polygon in the shape of a "T" Tetris piece can't be tiled with dominoes at all.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
greentreeroad
484 posts
#23 • 2 Y
Y by Adventure10, Mango247
Weirdly, a shape consists of a 3*3 square without the central square doesn't have unique tiling.

AAC
B C
BDD

BAA
B C
DDC

I don't think this is a polygon in strict definition. But obviously any correct proof needs to address this.(i.e. contains some argument regarding to no "holes" inside) Anyone notice this?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MellowMelon
5850 posts
#24 • 2 Y
Y by Adventure10, Mango247
The assumption that the polygon has no internal gaps is critical to the proofs that do "suppose there are two tilings, take a 'cycle' of dominoes on which they differ, and get a contradiction using the interior."
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math154
4302 posts
#25 • 1 Y
Y by Adventure10
Here's (hopefully?) another proof for uniqueness. (I'm sure it's similar in spirit to other things above, so sorry for reviving if it's a bit redundant. Most of it is just setting up for the last few paragraphs.)

Click to reveal hidden text

Edit: OK so I was looking at these necessary and sufficient conditions for domino tilings to exist (since I thought they could simplify my roundabout way above), and it seems that Thurston's height function (which applies to chessboard polygons here; see section 4 here) provides a very natural setting for this problem (it's pretty close to what probability1.01 did, but I guess more unified), since it embodies the notion of path orientation really well (in any path with height changing $+1\pmod{4}$ from one vertex to the next, the color of the square on the left remains the same).

The idea is that if we set the height function to be 0 at some arbitrary point on the boundary, then there's a unique "maximal" tiling, which must be tasteful. For more details, refer to this paper, which also explores a lot further (if you can't access it most of the ideas are here).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathcool2009
352 posts
#26 • 2 Y
Y by Adventure10, Mango247
EDIT: Oops I misread the problem, this only works for rectangles
This post has been edited 4 times. Last edited by mathcool2009, Sep 27, 2016, 3:00 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6857 posts
#27 • 3 Y
Y by mathcool2009, v4913, Adventure10
@mathcool2009: the chessboard polygon need not be a rectangle.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6857 posts
#28 • 6 Y
Y by mathmaster010, v4913, HamstPan38825, AbdulelahAltaf, Adventure10, Mango247
Here is the proof of (a) from the official solutions, by induction: let $\mathcal P$ denote the chessboard polygon which can be tiled by dominoes.

Consider a lower-left square $s$ of the polygon, and WLOG is it black (other case similar). Then we have two cases:
  • If there exists a domino tiling of $\mathcal P$ where $s$ is covered by a vertical domino, then delete this domino and apply induction on the rest of $\mathcal P$. This additional domino will not cause any distasteful tilings.
  • Otherwise, $s$ is covered by a horizontal domino. Again delete this domino and apply induction on the rest of $\mathcal P$. The resulting tasteful tiling should not have another horizontal domino adjacent to the one covering $s$, because otherwise we could have replaced that $2 \times 2$ square with two vertical dominoes to arrive in the first case. So this additional domino will not cause any distasteful tilings.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6857 posts
#29 • 8 Y
Y by mathmaster010, v4913, HamstPan38825, k12byda5h, AbdulelahAltaf, jeteagle, Adventure10, Mango247
Here is my proof of (b): Suppose for contradiction there are two distinct tasteful tilings. Overlaying the two tilings on top of each other induces several cycles of overlapping dominoes at positions where the tilings differ.

Henceforth, it will be convenient to work with the lattice ${\mathbb Z}^2$, treating the squares as black/white points, and we do so. Let $\gamma$ be any such cycle and let $s$ denote a lower left point, and again WLOG it is black. Orient $\gamma$ counterclockwise henceforth. Restrict attention to the polygon $\mathcal Q$ enclosed by $\gamma$ (include points of $\gamma$ as part of the tiling).

In one of the two tilings of $\mathcal Q$, $s$ will be covered by a horizontal domino; in the other tiling $s$ will be covered by a vertical domino. We focus on the latter one. Observe that we now have a set of dominoes along $\gamma$, such that $\gamma$ points from the white point to the black point within each domino.

Now impose coordinates so that $s = (0,0)$. Consider the stair-case sequence of points $p_0 = s = (0,0)$, $p_1 = (1,0)$, $p_2 = (1,1)$, $p_3 = (2,1)$, and so on. By hypothesis, $p_0$ is covered by a vertical domino. Then $p_1$ must be covered by a horizontal domino, to avoid a distasteful tiling. Then if $p_2$ is in $\mathcal Q$, then it must be covered by a vertical domino to avoid a distasteful tiling, and so on. We may repeat this argument as long the points $p_i$ lie inside $\mathcal Q$. (See figure below; the staircase sequence is highlighted by red halos.)

Let $x$ denote the first point of this sequence after $p_1$ which is on $\gamma$, and WLOG that point is white (black case is similar). Let $y = p_1 = (1,0)$ so the line segment $\ell$ joining $xy$ has slope $1$ (in the black case use $y=(0,0)$ instead).

Now $x$ is tiled by a vertical domino whose black point is to the right of $\ell$. But the line segment $\ell$ cuts $\mathcal Q$ into two parts, and the orientation of $\gamma$ has this path also entering from the right. This contradicts the fact that the orientation of $\gamma$ points only from white to black within dominoes. This contradiction completes the proof.
Attachments:
This post has been edited 5 times. Last edited by v_Enhance, Mar 31, 2018, 1:37 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Happy2020
509 posts
#30 • 3 Y
Y by kevinmathz, Adventure10, Mango247
:o :o :o @v_Enhance how do you make those cool diagrams
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6857 posts
#31 • 4 Y
Y by v4913, HamstPan38825, Adventure10, Mango247
Asymptote ;)

Source
This post has been edited 2 times. Last edited by v_Enhance, Mar 31, 2018, 1:33 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awang11
915 posts
#32 • 3 Y
Y by kevinmathz, Adventure10, Mango247
I'm confused, isn't the first one a "distasteful tiling" as well?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6857 posts
#33 • 4 Y
Y by v4913, HamstPan38825, Adventure10, Mango247
awang11 wrote:
I'm confused, isn't the first one a "distasteful tiling" as well?

No, the color of the squares matters in the definition of the two illegal configurations.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Kalymat
1 post
#35
Y by
hello everyone,
I am new in this program. I love math a lot and i'm pretty good at it...sometimes. Can anyone please explain the question to me. I was lost. If a polygon is a closed figure why are it's sides situated on lines that pass through the interior of said polygon. and if it divides into unit suares why do i see 1x2 rectangles 9white and grey)?
This post has been edited 2 times. Last edited by Kalymat, Sep 19, 2023, 11:06 PM
Reason: i'm still confused about the rest of the question
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Math4Life7
1703 posts
#36 • 1 Y
Y by sabkx
Kalymat wrote:
hello everyone,
I am new in this program. I love math a lot and i'm pretty good at it...sometimes. Can anyone please explain the question to me. I was lost. If a polygon is a closed figure why are it's sides situated on lines that pass through the interior of said polygon. and if it divides into unit suares why do i see 1x2 rectangles 9white and grey)?

If you are new to olympiads I would not recommend starting with a 45m problem
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
XD012
3 posts
#37
Y by
An unsolved idea. For each domino, place an arrow pointing from white to black, so the bad $2\times 2$ squares are all counterclockwise.
Z K Y
N Quick Reply
G
H
=
a