LESSWRONG
LW

Comment Permalink

Find the number of ways to tile a 1000 by 1000 grid with white and black tiles so each tile is adjacent to exactly two tiles of the same color.

The adjacency condition means that colored regions will form simple closed loops since ends and splits are disallowed. The smallest allowed region is a 2x2 tiles. The basic "textures" will be checkerboards of 2x2 regions and longer alternating stripes or concentric rings.

There are two ways to choose the color of the first corner tile at (1,1) position. The two tiles adjacent to the corner, (2,1) and (1,2) must match the corner. This covers the first two diagonals.

This gives another choice for the color of the (3,1) tile - it can either match the corner or not. Choosing this tile's color constrains other tiles, specifically any tile (x,y) with x+y <= 5 (the next two diagonals). The (4,1) tile must match the (3,1) tile, the (3,2) tile must be different from the corner, the (2,2) tile must be different from the (3,1) tile, etc. All colors will be symmetrical about the x=y diagonal.

Each additional choice constrains another two diagonals until the corner is reached, at which point the entire rest of the grid is constrained (it symmetrically matches the first half). For a 2Nx2N grid, this results in N choices before the entire grid is constrained or 2^n tilings (this extends even to the single degenerate tiling of the 0x0 grid).

For a 1000x1000 grid, there are 2^500 tilings satisfying the condition.

See in context

42

[ Question ]

What are the best elementary math problems you know?

by Ege Erdil

20th Mar 2022

1 min read

12 84

42

I'm looking for math problems of a specific kind. Here are the conditions I hope the problems satisfy:

A good mathematician who hasn't seen the problem before should take anywhere from 30 minutes to 2 hours to solve it.
The solution should only involve undergraduate level maths. Difficult Putnam problems are a good benchmark for what kind of maths background should be required to solve the problems. The background required can be much less than this, but it shouldn't be more.
For whatever reason you think the problem should be more widely known. The reason is completely up to you: the solution might include some insight which you find useful, it might be particularly elegant, it might involve some surprising elements that you wouldn't expect to appear in the context of the problem, et cetera.
It's fine if the problem is well known, your examples don't have to be original or obscure.

Here are some examples:

If a polynomial with rational coefficients defines an injective map , must it also define an injective map $R \to R$ ? If yes then prove this is true, if no then find an explicit counterexample.
Prove that $Hom (\prod_{k \in N} Z, Z) ≅ ⨁_{k \in N} Z$ . In words, prove that homomorphisms of abelian groups from the direct product of countably many copies of $Z$ to $Z$ themselves form a group that's isomorphic to the direct sum of countably many copies of $Z$ .
If $f : R \to R$ is a continuous function such that the sequence $f (α), f (2 α), f (3 α), \dots$ converges to $0$ for every $α > 0$ , must it be the case that ${lim}_{x \to \infty} f (x) = 0$ ? If yes then prove this is true, if no then find an explicit counterexample.

They are all relatively famous but they should give a sense of the flavor of what I'm looking for.

Exercises / Problem-SetsLogic & Mathematics World Modeling

Frontpage

42

What are the best elementary math problems you know?

New Answer

New Comment

12 Answers sorted by
top scoring

Jacob_Hilton

Mar 29, 2022

170

A magician asks you to choose any infinite sequence of 0s and 1s, and to start reciting it until they say stop. They will then make a prediction of the form "p% of the next n digits will be 0", and they will be correct to within 1% at least 99% of the times they perform the trick. How is the trick done?

h/t Alex Arkhipov

[-]paulfchristiano3y40

A solution:

We'll describe a strategy for the magician that stops you sometime within the first $2^{k}$ bits and gets an expected squared error of exactly $1 / k$ regardless of your string. If we pick $k = 10^{6}$ , the strategy has a squared error of at most $10^{- 6}$ , and so gets within 1% at least 99% of the time. This requires the magician to wait for up to $2^{10^{6}}$ bits. I suspect that's roughly optimal but haven't checked the construction carefully.

The strategy is to pick a random $0 \leq ℓ \leq k$ , then pick a random $1 \leq m \leq 2^{k - l - 1}$

... (read more)

[-]paulfchristiano3y30

I found this puzzle fun and I feel like I learned something useful about math when you gave it to me a few years ago.

[-]acgt3y20

Curious what the solution to this one is? Couldn’t figure it out

2paulfchristiano3y

I posted it in another reply.

[-]Ege Erdil3y10

I'll be thinking about this problem for the next hour or so unless something comes up, so I'll be writing my thoughts down here if I think they are important.

A couple of preliminary observations:

The magician must be playing a mixed strategy. This is easy to see since otherwise a copy of the magician playing against him could know when he stops and could know his prediction and deliberately falsify it no matter what.
It's not enough for the prediction after the stopping to be random, the stopping time itself must also be random. This is because if I

... (read more)

1Ege Erdil3y

3paulfchristiano3y

This seems like it nearly works, but

[-]philip_b3y10

Is the following a correct reformulation of your problem?

Say that a magician's pure strategy is a function on finite bitstrings which returns either "go on" or "stop" with a positive integer $n$ and a frequency $f$ of zeros.

A magician's mixed strategy is a probability distribution over magician's pure strategies. (Btw, I'm not sure what kind of sigma-algebra is suitable here.)

A player's mixed strategy is a probability distribution over infinite bitstrings.

A magician's mixed strategy together with a player's mixed strategy define, in the obvious way, a probabil... (read more)

5paulfchristiano3y

I think you can slightly simplify to say: the magician has a probability distribution over strategies, such that for every sequence the magician wins with probability 0.99.

1philip_b3y

Yes, indeed.

Yair Halberstadt

Mar 21, 2022

A countably infinite number of people are each assigned a hat that is either red or blue.

Without communication, they must each guess the color of their hat. The cannot know of each others guesses.

Show that there exists a strategy by which only a finite number of people will guess incorrectly.

[-]philip_b3y*70

I've formalized this problem in Coq with mathcomp. Yeah, idk why I decided to do this.

From mathcomp Require Import all_ssreflect.
Set Implicit Arguments.
Unset Strict Implicit.
Unset Printing Implicit Defensive.

Definition hats_assignment : Type := nat -> bool.

Definition policy_of_one_person (n : nat) : Type :=
  {policy : hats_assignment -> bool &
   forall ha : hats_assignment,
     let ha' := fun m => if m == n is true then ~~ (ha m) else ha m
     in policy ha == policy ha'}.

Definition strategy : Type :=
  forall n : nat, policy_of_o

... (read more)

1Ege Erdil3y

This is great.

[-]Ege Erdil3y20

For clarification, the people can all see the color of other people's hats, right? If so, then:

The people agree in advance (using the axiom of choice!) on a set of representatives for all equivalence classes in $2^{N} / \sim$ , where two bit sequences are equivalent under $\sim$ iff they differ in only finitely many positions.

When they are guessing, they all know the equivalence class they are in and they guess the color for their hat that is implied by the agreed upon representative of that equivalence class. By construction, only finitely many of them can guess incorr

... (read more)

2Yair Halberstadt3y

Yes they can see each others hats.

[-]philip_b3y10

Do people have common knowledge of an ordering of all of them?

2Yair Halberstadt3y

We can assume that they can each magically agree on the same strategy, and that as they are countably infinite they can find a common ordering of them.

Yair Halberstadt

Mar 20, 2022

Show that every countably infinite graph contains either a countably infinite complete subgraph, or a countably infinite edgeless subgraph.

[-]Ege Erdil3y60

Another nice one. I liked this one enough for a strong upvote. Here is my solution:

Say the graph is $G = G_{0}$ . If $G$ has no vertices of infinite degree then it has a countably infinite edgeless subgraph: we just pick any vertex, throw away its neighbors, pick another vertex, throw away its neighbors, etc. Since we can always do this, we end up picking countably infinite vertices without any edges between them, so we're done.

Now suppose $G$ has at least one vertex of infinite degree, say $v_{1}$ . Let $G_{1}$ be the subgraph consisting of the neighbors of $v_{1}$ and all the edg

... (read more)

[-]AprilSR3y10

This sounds obviously false to me? Why can’t you have a countably infinite graph where all vertices have degree 2?

2Algon3y

Biject the graph to z, drop all odd edges and you get a countably infinite subgraph. The key point is that you're looking for any subgraph that is complete or edgeless.

3AprilSR3y

Ah! I see.

Ege Erdil

Mar 23, 2022*

There are paratroopers that simultaneously land on the plane $R^{2}$ at independently and identically distributed positions, drawn from a distribution with density $p$ . After landing, each paratrooper sleeps for independent and identically distributed times drawn from a distribution with density $q$ on the positive real numbers. Before they wake up they are unable to take any action other than standing at the position they've landed on.

All paratroopers have two devices with them: an infinite precision radar and a detonation button, both of which can only be used once.

Using the radar tells them the exact positions of all other paratroopers relative to the current position of the radar user. (This is important - the paratroopers don't have a compass to fix global directions such as north and south, and the radar only gives them information about relative positions.) This is the only way the paratroopers have of getting information about each other's locations: aside from all of them being able to use the radar once, they have no other way of getting information about the location of other paratroopers even if they are standing on the same spot at the same time. The radar also doesn't tell the user which paratroopers are at which locations, it only displays every location (possibly with multiplicity in the case of coincidence) at which there is a paratrooper.

The mission of the paratroopers is to press their detonation buttons all at the same location on the plane, though not necessarily at the same time. In other words, they all need to coordinate to go to the same point and press the detonation button once they are there, after which they are once again free to move as they please until the mission is either a success or a failure.

As a final technical detail, both density functions $p$ and $q$ are nonzero on their whole domain: this is $R^{2}$ for $p$ and $R^{\geq 0}$ for $q$ .

Assuming that the paratroopers can agree on a strategy before the mission begins, show that there is a strategy with which they can win almost surely (with probability equal to 1).

[-]DaemonicSigil3y40

Cool problem, I think I may have (at least a sketch of) a solution. The way the paratroopers are allowed to move wasn't specified in the problem, but it would be too easy if they were allowed to just teleport around to arbitrary locations, so I'll assume that their movement has to be described by continuous functions.

Everyone will head towards a point chosen by the first paratrooper to wake up. Thus the first paratrooper to wake up must somehow "mark" himself. Further, he must mark himself instantly, right after waking up. This seems impossible, since th

... (read more)

1Throwaway23673y

Isn't moving after reaching the destination superfluous? Everyone can see where to go as the radar gives position with multiplicity and with probability 1 there won't be another pair on the same point.

1Ege Erdil3y

For some solutions it is. I wanted to allow it anyway in case someone found a solution which requires it.

1Throwaway23673y

I get that, I am talking specifically about DaemonicSigil's solution. I understand that you need to move to know who is the tail and the first trooper, but knowing who those are is not necessary to know the destination, so I'm wondering why they keep moving.

2Ege Erdil3y

Ah, then yes, I think it's superfluous.

1Ege Erdil3y

[-]paulfchristiano3y*30

Here is a kind of long solution that I think works (ETA: for the case $n = 3$ )

This was posted on our house puzzle slack before, it was one of the few problems that wasn't solved though it didn't get as much love as some of the harder problems.

I'd expect that a fairly large fraction of working mathematicians wouldn't get it in 2 hours (and similarly for most of the hard Putnam problems) though I may be underestimating their ability to solve contest-like problems or it may have a simpler solution than this one.

Every paratrooper will use their radar as soon

... (read more)

2paulfchristiano3y

Note on this solution (potential bug in the solution / problem statement, depending on exactly what you meant, this would also break the other proposed solution): Small bug in solution that is easy to patch: I would currently guess that the problem is solvable with adversarially chosen points / wakeup times, and with no access to randomization. But it's very unclear and it involves a much more annoying argument.

1Ege Erdil3y

Responding to the points in your note:

1Ege Erdil3y

I didn't sanity check this solution yet but it's a very different idea from what I had in mind. Does it only work in the case n=3?

2paulfchristiano3y

This solution only works for n=3. I think it's probably possible to adapt it to n>3, but it's clearly much more complicated and I suspect a different approach is easier. Compared to DaemomicSigil's solution, I think the main advantages in the n=3 case are:

7PatrikN3y

For n = 3 you can exploit that the soldiers land on a circle for a neat solutions (meet at the soldier opposite to the longest circle segment walking along the arcs).

3paulfchristiano3y

Oh man, that's a way better solution. Seems like the same basic idea as mine (and converges to the same point), it just uses a super natural/clean set of trajectories instead of a handwaving argument that they must exist. It seems like you can probably also generalize that to n>3.

1Ege Erdil3y

What's your idea for generalizing this to n>3? Seems nontrivial to me. I would be interested if something like this ended up working for large n because my solution leans very hard into the fact that the radar has infinite precision. I'll post it in spoiler tags as a direct comment to the question so people can examine it, maybe it helps inspire some ideas.

3paulfchristiano3y

Definitely doesn't seem trivial to generalize, and I'm not sure if this is actually easier or harder than my solution. It seems pretty interesting to find something that works for imprecise radar (in the sense that the error probability goes to 0 as radar error approaches 0). Idea for n=4: * Let AB be the closest together pair of points. Let AC be the second-shortest distance involving either A or B. Then we all decide to approach point A. * If I'm not one of ABC, then I start by moving very far away from everyone else so that I won't disrupt anything. Then I circle around until I get on the other side of A, and finally I approach A in such a way that I'm always closer to A than either B or C. This guarantees that A will remain the target point. * Hopefully it's also possible to define approaches for B and C that preserve the fact that A is the target: * Point B would need to ensure that it's always further than AC away from any non-A point, and that it's always closer to A than the next-closest distance between a pair of points. So the valid region for B to walk in is a circle centered at A minus a bunch of circles centered at other points, and the question is whether those other circles can disconnect A and B * Point C needs to ensure that it never gets within AB of any non-B point, so its valid region is the complement of a union of circles, and the question is whether it can be disconnected from A. * I think I can use the same tricks from my original solution to avoid worrying about the possibility of multiple points moving at once. You still have to deal with the final instant of the trajectory just as before, which is another annoying geometry problem. * I'm maybe 50-50 that this exact approach would work, but it feels like something will. If I wanted to solve in general I'd probably just keep trying larger and larger n and see if any general solution became clear. Designating "one of the two points in the closest pair" breaks down immediately for

[-]PatrikN3y100

For n = 4 the following trick works, but does not really have the same flavor as the n = 3 case:

If the soldiers land in a convex position (they are the corners of a convex quadrilateral) then meet at the intersection of the straight lines connecting the opposite soldiers. If they land in a triangle with one soldier in the interior, meet at the soldier in the middle.

Here the soldiers are forced to walk in straight lines.

It would not surprise me if there are tricks like these for some more n, but I don't see a general strategy. I think there is something you can do for odd n that is quite different from the other solutions so far, but I have not checked it fully yet and worked out what it requires from the radar.

8paulfchristiano3y

Wait, can we just

1PatrikN3y

That’s pretty cool, I wonder why I did not remember this concept.

1Ege Erdil3y

2paulfchristiano3y

Now I feel silly again for having such an ugly solution. I do feel like we can probably generalize the super ugly solutions: it seems like we have plenty of degrees of freedom and so the challenge is about how to compactly describe a strategy rather than coping with any fundamental difficulty. (But of course there may be some fundamental obstruction that just isn't obvious yet.)

1Ege Erdil3y

By the way, as a bit of trivia about the problem: I don't know who came up with it but the person who gave the problem to me said that there is a nice solution which works for all n≥3 and only fails when n is even and everyone's starting positions are collinear. I haven't made much headway into finding such a solution yet. I'm wondering how helpful it is to try cases with small n and hope a general pattern is going to emerge instead of trying to find a solution from scratch that at least works for all sufficiently large n. It's difficult to decide which you want to spend your time doing.

2paulfchristiano3y

Oh, I think I just found that solution in parallel (or at least I found a solution with exactly the same failure condition). It was directly inspired by PatrikN's solution. (Although I didn't realize until after writing it that it is literally a generalization of PatrikN's solution.)

[-]ESRogs3y30

Does the radar tell the paratroopers which other paratrooper is where, or just that there is some unknown paratrooper at each spot? In other words, are the paratroopers labeled on the radar?

3Ege Erdil3y

They aren't, otherwise the problem would be trivial since everyone could just agree on a person to be the target beforehand. I've edited the question to clear this up.

2ESRogs3y

Gotcha, in that case:

3Ege Erdil3y

So a general bit of advice for this problem is that the solution I have in mind is not trivial at all - it involves plenty of cleverness to come up with and some careful accounting of all of the edge cases to prove that it works. My solution is most likely not the simplest possible but my suspicion is that no solution is going to be as simple as the ones people have proposed thus far. If you think you have a simple solution, your solution is probably wrong.

[-]Ege Erdil3y20

Here is my solution:

For $n = 2$ the solution is easy, as others have pointed out.

For $n \geq 3$ , everyone executes the following algorithm (which works even if everyone has to move at a constant speed):

when you wake up:
    if (there exists a rational angle):
        let angle = ABC
        if you're B:
            press the button, then stand still
        else:
            walk towards B in a straight line
            press button at the point B
    else:
        let {B, C} be the pair of points with the shortest distance
        let B be the one with the larger

... (read more)

[-]Richard_Kennaway3y20

I'm not seeing what the time delays have to do with it, nor the probability distributions. Cannot they win with certainty (not just almost surely) by going to the average of all their positions?

1Ege Erdil3y

3Richard_Kennaway3y

I see, that’s where the times come into it. They have no way of knowing when everyone has woken and used their radar.

[-]PatrikN3y10

Everyone uses the radar once they wake up. The two closest soldiers go towards each other on a straight line. Once they meet up and possibly wait for the other one to wake up they are free to visit all other soldiers in any order, when they are all together they can detonate. The important property is that the initial shortest distance is unique almost surely.

1Ege Erdil3y

1PatrikN3y

Mar 21, 2022

Prove or disprove the existence of random variables X_n so that the expected value of X_n goes to infinity as n goes to infinity but X_n goes to 0 almost surely (maybe not as much of a problem, but a pretty useful thing to think about for people who use EV calculations to make decisions).

Find the number of ways to tile a 1000 by 1000 grid with white and black tiles so each tile is adjacent to exactly two tiles of the same color.

First is much easier than 2nd.

[-]Measure3y20

Find the number of ways to tile a 1000 by 1000 grid with white and black tiles so each tile is adjacent to exactly two tiles of the same color.

There are two ways to choose the color of the first corner tile at (1,1) position. The two tiles adjacent to the corner, (2,1) and (1,2) mus

... (read more)

1Yair Halberstadt3y

I can only find 4 tilings of the 6 by 6 grid: 110011 110011 001100 001100 110011 110011 And 111111 100001 101101 101101 100001 111111 As well as their inverses. What am I missing?

7Measure3y

111100 100100 100111 111001 001001 001111 This one, its rotation, and their inverses.

[-]Ege Erdil3y20

About the second problem:

I've determined computationally that for an $n \times n$ grid the number of tilings is $2^{n / 2}$ if $n$ is even and $0$ if $n$ is odd, but I don't have a proof of this fact yet. I'll be looking for one - the answer looks quite nice so there ought to be a neat argument for seeing why it's like this.

More precisely, it looks like the possible tilings correspond to the ways of tiling the first row of the grid with 2x1 white or black dominoes. It's easy to see that the first row has to be of this form and that any such first row can't correspond to more

... (read more)

[+][comment deleted]3y10

Deleted by acgt, 03/21/2022

Reason: Misread question

[-]Yair Halberstadt3y10

For the 2nd, does adjacent include diagonals?

3Measure3y

If it does, I don't think there are any valid tilings.

1[comment deleted]3y

[-][anonymous]3y10

My University has a problem sheet question that presents the first problem in a nice way that feels more real-worldy

interstice

Mar 20, 2022

Find the maximum cardinality of a set of disjoint figure-eights in the plane, and prove that it is the maximum.

Let a = 1/n be the reciprocal of a positive integer n. Let A and B be two points of the plane such that the segment AB has length 1. Prove that every continuous curve joining A to B has a chord parallel to AB and of length a. Show that if a is not the reciprocal of an integer, then there is a continuous curve joining A to B which has no such chord of length a. [Source: Challenging Mathematical Problems with Elementary Solutions vol.2]

[-]Ege Erdil3y30

I forgot about this one. For the first problem:

You can get an injection from any collection of disjoint figure-eights on the plane to $Q^{4}$ by picking any rational point in the interior of each of the two circles making up the figure, so there can only be countably many such disjoint figures. This is an injection because if another figure-eight had the same rational points as its representative, then it's easy to show that the two figures must intersect somewhere.

[-]Ege Erdil3y10

I don't understand your first question. Can you clarify?

1interstice3y

By a figure-eight I mean a curve consisting of two topological circles that meet at a single point, e.g. Then you want to find the maximal cardinality of a set of these, such that no two intersect. Obviously there can be at least countably many; the question is whether there can be more.

1Ege Erdil3y

Ah, I understand. Thanks.

Algon

Mar 20, 2022

Let be an ordinal s.t. $C a r d (α) > C a r d (R)$ . Let $α^{ω}$ be the cardinality of functions from $ω$ to $α$ . Is $C a r d (α) = α^{ω}$ ? If so, prove it.

[-]Ege Erdil3y*10

Nice question. I'm providing my solution below, spoiler protected so people can attempt to solve the problem on their own.

By König's theorem

$ℵ_{ω} = \sum n \in ω ℵ_{n} < \prod n \in ω ℵ_{ω} = ℵ_{ω}^{ω}$

so the answer is no. This is also the smallest counterexample that ZFC should be able to decide, since GCH is undecided in ZFC and if GCH is true then $ℵ_{α}$ will have a base two logarithm for any successor ordinal $α$ and any infinite $κ$ that has a base two logarithm will satisfy $κ^{ω} = κ$ .

interstice

Apr 28, 2023

Define a ribbon rile of length to be a 2D configuration of $n$ squares, constructed from a starting square by repeatedly adjoining a square above or to the right of the most recently added square. Prove that the number of tilings of a $n \times n$ square by length- $n$ ribbon tiles is $n!$

Ege Erdil

May 29, 2022

What do the following problems all have in common?

What's the number of permutations in the symmetric group on letters $S_{n}$ without fixed points? What happens to the ratio of this number to the size of the group $| S_{n} | = n!$ as $n \to \infty$ ?
Suppose you draw $n$ samples with replacement from the set $S = {1, 2, 3, \dots, n - 1, n}$ uniformly at random. Say the set of all elements you get is $A$ , where we don't distinguish between two draws of the same element. What's $E [| S - A |]$ , i.e. the expected value of the cardinality of the set difference $S - A$ ? What happens to $E [| S - A |] / n$ as $n \to \infty$ ?
Two players A and B play the following zero-sum game: they take turns sampling from a probability distribution on the real numbers $R$ with a continuous probability density function. The first player to draw a value that's smaller than the maximum of all previous values drawn by both players loses. If A goes first, what's the probability that B wins the game?

Shoutout to Jane Street for this problem!
The secretary problem: there's a totally ordered finite set $S$ with distinct elements. You know the cardinality $n$ of $S$ . You play the following single-player game: you get to sample one element at a time from $S$ without replacement and uniformly at random. At any point you may choose to stop sampling and keep the last element you've sampled. You win if you halt on the maximum element of $S$ and lose otherwise.

For $n$ large, what's the strategy that maximizes the chance of victory in this game? What's the probability of victory achieved by the optimal strategy?

[-]acgt3y-10

The answer to all of them is 1/e?

2Ege Erdil3y

That's right :) There's a type of problem that is recognizably a "1/e problem", in the sense that you expect the answer will somehow involve 1/e, but I haven't been able to make this intuition precise. What properties about a problem make it likely that 1/e shows up? Some of the above problems involve use of the inclusion-exclusion principle, which is a typical way 1/e can show up in these problems, but e.g. the secretary problem does not.

Ege Erdil

Mar 28, 2022

Consider the following game: there are players standing in a row, each with a tower of countably infinitely many red or blue hats on top of their heads. The probability of any hat being red is $1 / 2$ and likewise for any hat being blue, and the colors of the hats are jointly independent. Each player can see all of the hats on the heads of everyone other than themselves but they can't see any of their own hats.

To win the game, the players must all simultaneously guess a natural number (the number can be different for different players) and ensure that all of the hats on their own heads in the position they named from the bottom of the tower are red. For example, if three players are in the game and their guesses are $1, 5, 13$ , then they win if the first hat from the bottom on player 1's head, the fifth hat from the bottom on player 2's head and the thirteenth hat from the bottom on player 3's head are all red. If even one of them is blue, then they lose.

The players can all agree on a strategy to execute as a group beforehand, but can't communicate with each other once the game begins.

Prove that there is a strategy with which the players can win with probability $Θ (1 / log N)$ .

Ege Erdil

Mar 22, 2022

Let be the set of integers $n \geq 2$ such that all groups with a proper subgroup of index $n$ also have a proper subgroup of index strictly less than $n$ .

Give an explicit description of $S$ .

Rendering 5/35 comments, sorted by

top scoring

(show more) Click to highlight new comments since: Today at 11:10 AM

[-]Yair Halberstadt3y*70

Show there are no integer solution to for $n \geq 3.$

An excellent solution should take slightly more space than this comment ( ͡° ͜ʖ ͡°).

[-]Pattern3y20

A good mathematician who hasn't seen the problem before should take anywhere from 30 minutes to 2 hours to solve it.

I wouldn't have necessarily characterized that as

the best elementary math problems you know?

[-]Ege Erdil3y30

That's fair, though I'm not sure what else to put in the title in this case. It's necessarily going to be a compressed version of what I'm actually asking for.

[-]Pattern3y20

A good mathematician who hasn't seen the problem before should take anywhere from 30 minutes to 2 hours to solve it.
The solution should only involve undergraduate level maths. Difficult Putnam problems are a good benchmark for what kind of maths background should be required to solve the problems. The background required can be much less than this, but it shouldn't be more.
For whatever reason you think the problem should be more widely known. The reason is completely up to you: the solution might include some insight which you find useful, it might be particularly elegant, it might involve some surprising elements that you wouldn't expect to appear in the context of the problem, et cetera.
It's fine if the problem is well known, your examples don't have to be original or obscure.

'Good 0.5-2 hour undergraduate problems you think should be more widely known.'

Overall, the tricky thing about it is finding a problem that meets all those requirements.

https://www.lesswrong.com/posts/R82zuc4MZXvG2dJXY/if-your-solution-doesn-t-work-make-it-work

This has a good problem, that might take awhile if you're not familiar with linear algebra. It might or might not be useful to spreading basic understanding of linear algebra, or what (some of) that is about.

Is this good mathematician an undergrad?

The background required can be much less than this, but it shouldn't be more.

I didn't read this the first time through, and I think it suggests me posting the above link here, even if it doesn't take long enough.

[-]Yair Halberstadt3y20

This has a good problem, that might take awhile if you're not familiar with linear algebra

The problem is very simple without linear algebra - just notice that relative parities are preserved (i.e. if there are an even number of reds and an odd number of blacks, then after any sequence of moves they will always have opposite parities).

The given solution is to highlight a strategy, not the easiest way to solve the problem.

Moderation Log

Curated and popular this week

12 5

42

[ Question ]

What are the best elementary math problems you know?

42

42

12 Answers sorted by top scoring

Mar 29, 2022

Mar 21, 2022

Mar 20, 2022

Mar 23, 2022*

Mar 21, 2022

Mar 20, 2022

Mar 20, 2022

Apr 28, 2023

May 29, 2022

Mar 28, 2022

Mar 22, 2022

12 Answers sorted by
top scoring