The Easiest Problem on the Hardest Test [2017 Putnam Competition A1] 

you're right! when i was recording, i was thinking "well, i don't want to accidentally double up on any family of multiples." but i guess i was too aggressive in what i didn't write :)

@@polymathematic It's cool. I really liked this problem!

no points :P

1 + 5k. Given the pattern, k starts at 1

@@polymathematic For consistency with whats normally taught, I think you should have either used k is natural number or positive integer instead of just "integer"

thank you! glad you liked it :)

i think writing out the proof would be pretty boring on video, but i have often wondered how many points i could get on the real thing. i didn't know about it when i was in undergrad, unfortunately. maybe i'll go back to school someday and try it out :)

oh man! well, you should still be proud of getting several problems right. but yeah, even with problems like this, it's much easier to be doing it under no time constraint for fun years later than it is to try and answer on a timed test surrounded by other eager math students :)

@xxdxddddffwfegfg your undergrad institution has to offer it, and this year's took place a few weeks ago. but if you're interested, you can see more about it here: www.maa.org/math-competitions/putnam-competition

thank you!

yeah, the typical putnam problem, even A1, destroys me. that's why i love this one so much :)

thank you!

well that's good news, 'cause i love that you're watching it too!

i'll check that out! i only became familiar with the competition about 5 years ago, and i've never dived that deep in the archives.

You basically have to prove 2 things: 1. The set as described has all three properties. 2. Any set with all threeproperties contains the described set. For 2. i would first prove that if x is in the set then x+5 is in the set. Then proceed to show that 2,3,4,6 are in the set by giving a conrete construction as was done in the video. This completes the proof.

The answer would not be {1, k, 2k, …} for most k. For example, if we take k = 7, we get the squares mod 7 are: n -> n^2 mod 7: 0 -> 0 1 -> 1 2 -> 4 3 -> 2 4 -> 2 5 -> 4 6 -> 1 We start with a number that is 2 mod 7. We thus have a square of a number 2 mod 7 in S, which will give us a number 4 mod 7. However, if we square this number, we get something 2 mod 7, but we already had numbers 2 mod 7 in S, so that didn’t help us get new numbers in S. Um… it looks like 5 squares is 4 though, so the square root of some number that is 4 mod 7 is 5 mod 7. Thus, we can get numbers that are 5 mod 7. The same works to get us numbers 3 mod 7, because the square root of some number 2 mod 7 is 3 mod 7. However… alas, we don’t have any numbers 1 mod 7, so numbers that are 1 mod 7 or 6 mod 7 don’t have to be in S. Thus, numbers that are 0, 1, or 6 mod 7 need not be in S. The pattern for an arbitrary k is not obvious to me, and you could probably gain deeper insight with number theory and knowing theorems about squares mod k, but I don’t know number theory well enough to give an answer beyond “there’s no simple pattern for odd k.”

@@myrus5722 Oh wow you're right! At least we know if 2 is a primitive root mod p then we'll for sure hit all the congruence classes mod p and (I think?) that means the answer is indeed {1, p, 2p, ...}. But I also don't know enough number theory to say much more.

absolutely! I got the same vibe after messing around with it

you are off in the sense that we can work from any perfect square to its square root being in the set, but not the other way around. Obviously it doesn't really matter, 'cause it turns out that both 2 and 4 are in the set, but 2 being in the set doesn't necessarily imply that 4 is. glad you liked the video! thanks for watching :)

@@polymathematic ​ @Tom Heyworth Thanks, now I understand completely!

S with 1 contains S without 1, so it can’t be the smallest be the definition stated in the problem. Thus, I think you are correct.

exactly. 1 definitely COULD be in the set, in the sense that it obeys the rules, but it doesn't HAVE to be in the set, 'cause we'll never "collide" with its square (being that it is the only positive integer that is its own square).

i'm not sure about theorems, but it's definitely related to how squares progress mod 5. for example, the reason numbers ending in 4 and numbers ending in 6 both square to make numbers ending in 6 is that 4 is -1 mod 5 and 6 is 1 mod 5. since both -1 and 1 have the same square (positive 1), they end up squaring to make the same 1 mod 5.

very nice!

@@polymathematic Thank you, love your videos !

lol

i *definitely* got collatz vibes while working through it. here's my only collatz take though: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-d0W1wbNgMkg.html

Sure! Once a given number is confirmed in the set, every number that is some multiple of 5 bigger than that number is also in the set. For example, at the start, we confirmed that once 2 was in the set, so were 7, 12, 17, etc. For 2916, that means that 2921, 2926, 2931, and so on are all in the set. You’d have to add the fives for a very long time, but eventually you’d get to 65536, because we can tell we’ll have all the numbers bigger than 2916 that end in 1 or 6 (since that’s what happens when you keep adding fives). Does that help?

if i remember correctly, it specified that S was a set of positive integers.

@@polymathematic Yes, but it doesn't specify what n is. Do we just assume that n has to be a positive integer? Otherwise I'd say such a set doesn't exist.

not quite. none of the numbers ending in 5 or 0 are in the set, but lots of numbers ending in 1 are in the set. it's just that 1 *itself* is not in the set. for example, another path for getting 11 is to go from 54² = 2916 to 3136 which is 56². Once you have 56² you must also have 56, which gives you 61, 66, 71, etc., all the way up to 121. Since 121 = 11² , that means you also have 11, and then 16, 21, 26, etc.

very nice!

very nice!

hmm, depends on the level, i suppose. i work mostly with high school students and below, so those competitions rarely prioritize proof over the solution itself.

I have a few comments. First of all, you should read the question more carefully. You use in your solution that if n is in S, then n^2 is in S, but the rule that is given is the other way around: if n^2 is in S, then n is in S. Something that is given, however, is that when n is in S, then (n+5)^2 is in S. This does mean that if 5k+2 is in S for all nonnegative integers S, then (5k+7)^2=5(5k^2+14k+9)+4 is in the set for all nonnegative integers k. Using your logic, we can conclude that "5k+4 is in the set". Indeed, we have shown that there are element of the form 5n+4 in our set, but this does not mean 5n+4 is in the set for all nonnegative n, since not all those n can be written as 5k^2+14k+9 (actually, very few of the can be). Even when we take the smalles k possible, k=0, we only get that 49 is in the set. Nothing can be concluded for the numbers 4, 9, 14, 19, ...., 44. Also, you say you will show that 5k+3 and 5k+4 are in the set for all nonnegative integers k, but that 5k+1 is in there for all strictly positive integers k. However, your arguments for the cases 1 and 4 is exactly the same. How come the same argument gives a different outcome? Clearly, 5*0+1 does not need to be in S, so why should 5*0+4? Furthermore, never in your argument do you show that 3 is in S. you rightfully claim that if 8 is in S, then 5(k+1)+3 is in S for all nonnegative integers k. Then, you claim that "5k+3 is in S". You should be more precise. You have indeed found a LOT of values of k for which this is true (namely all k >= 1), but you sweep the case k=0 under the rug and don't mention it, while the truth is you did not show 5*0+3 = 3 is in the set. And for the last of my comments, you say this solution is "without computing", yet you say that we conclude 8 is in S just like in the video. This is a very clear computation, and it is necessary! Your solution is not worthless, as you indeed show there are numbers of the form 5a+4, 5b+1 and 5c+3 in S, but the next step would be to show that the SMALLEST numbers of these forms that appear are 4, 6 and 3. These require computations and it is those you are missing. I don't mean to discourage you or be mean/annoying. The lesson is just to be more precise in your statements and claims. Try to concretely understand what you are saying and check every little step. Maybe you can correct your solution. Good luck!

@@thiantromp6607 You are 100% correct squaring 5k+2 to get to 5k+4 and 5k+1 is a big mistake that i didn't see... I also rushed and didnt show that 3 and 4 are in the set as you said but thats not really a problem it s pretty easy to show if we have all other numbers. Good thing i posted the solution i would have probably go on thinking it was correct and thanks for the comment.

2 + 5k and 3 + 5k are the square roots of 4 + 5k, so you need to be careful to find a perfect square with its square root in the second form I.e. 64 and 8.

No, rule 2 isn't saying that *only* perfect squares are in the set S. It's saying that *if* some perfect square is in the set, then its square root is also in the set. Rule 1 (that 2 itself is in the set) is there to guarantee set S isn't just the empty set, which would certainly satisfy rules 2 and 3, and would obviously be the smallest such set.

@@polymathematic Hmm, my point is that no where is n defined as an integer in the question. The first thing I did was take the value I knew was in the set: 2, and feed it into rule 2. n^2 = 2, therefore n (which is root2) are in the set, but the set contains only positive integers. Contradiction, therefore no such set exists. All that needs to be changed in the question is to say n is positive integer.

@@jamesrockybullin5250 ​ “Let S be the smallest set of positive integers such that…” is literally the first thing in the video

@@evanlewis2349 But what about n?

@@jamesrockybullin5250 If S is a set of integers and n is in S, then n must be an integer too.

i'll check it out!

I’ve got another 2 hours and 50 minutes to write it up my man :)

lol, true. 220 away.

no worries! I know it can be tough to follow. given any number in the set, we're guaranteed every number that is bigger than that by a multiple of five based on the last two rules of the problem. since 65536 is greater than 2916 by 62,620, and since 62,620 is a multiple of 5, we're guaranteed to have it in the set. then by the second rule, you're guaranteed 256, 16, and 4 (and 2 for that matter, though we were given 2 so that's not as important). hope that helps!

@@polymathematic I did not ask for the explanation for myself. I solved the problem some time ago and generated them differently. I meant that it should have been explained in the video, not only "because it ends in 6" but, more fully, as you explained here, the fact that any square that ends in 6, greater than 2916, it is written as 2916+a number that ends in 0, so it is of the form a number from S + multiple of 5, therefore it is from S. But I congratulate you for your solution that can be understood and taught to middle school students, without congruences in Zn. Respectfully.

hmm, i dunno about that. some problems are genuinely difficult. in this case, maybe it could be better written, but the explanation is there because the possible sets S as described in the question have an infinite number of elements. so it's not really correct to say S is the smallest such set in a numeric sense. instead, it's the smallest set in a set-theoretic sense.

I crafted a simpler explanation since it also flustered me (I was pretty good with Math back in High School, but the question befuddled me) Suppose that S is an array [a, b, c, d...] with the following criterion: 1) 2 must be one of the values of S 2) n (which is a positive integer) must be one of the values of S 3) For any value x in the array, if it is a square value, its square root must also be in the set (ex. 4 leads to 2 is in the array) 4) For any value x in the array, the value (x+5) squared must also be in the set (ex. 1 leads to 6 squared = 36 is in the array) Create a simple array of all positive integers that are not guaranteed to be a part of the set, regardless of what n is equal to. After watching the video, I still have no clue how the idea of it being the "smallest" set is even accurate since there are no constraints to the set, meaning that at least in theory it has infinite numbers within it. If the rule that 2 is part of S wasn't a thing, the framing of the question would make me think that the fives and zeroes would be the smallest set since they wouldn't be able to get to the other numbers much as numbers like 5, 10, 15 cannot be reached from beyond the fives and zeroes column. Similarly, saying "not guaranteed" makes it so that 1 has to be part of this new set, rather than being a possibility for the original if n was initially equal to it. Also, back when I learned mathematics, we had a thing called the "variable" that could only apply to a single value, so it irks me that n is not being used as a variable here, but rather as a substitute for any number. I have to an extent let go of Math for the past few years since I have realized that much like a politician's propaganda, it is oftentimes intended to be purposefully deceitful which punishes anyone who cannot interpret the proctor's foggy ideas. Math is not the only academic field where this is problematic, although I believe that it is inexcusable that early 20th century language is being used in a world that has a lot of 21st century jargon. There is no incentive for institutions to give basic examples if they want to set the greater number of people on the right path, especially in a changing world in which we have access to a whole library of digital resources. This would not be so different from being provided with a formula sheet so that individuals don't have to mindlessly memorize useless information or how many professors offer take-home exam options because the limited duration of time in a classroom setting is 99% of the time not representative of a student's full potential.