Shenhui Yang from Wolfram Alpha walks through solving contest math problems using Wolfram Language. He tackles seating arrangements, perfect squares with repeated digits, and a train collision problem where the answer connects to harmonic numbers, showing how to avoid rejection sampling and link results to known sequences.
Chapters
All right. Okay. Hi everyone. Thanks for coming to the Wolfram Live R and D session. My name is Shenhui Yang. I work for Wolfram Alpha team and I would like to solve challenging math problems during the work time and off the work time because I really like those interesting problems and you can find on Internet. And I have done a couple of the problem solving sessions during Wolfram conference and most of them are already on YouTube. So you can just find a warframe technology channel and find those problem solving sessions. If you are interested in those challenging problem solving techniques and how to use Wolfram language and other resources to help you understand the solutions and promote your understanding of what's behind and the background of those problems. Okay, so today I'm going to first introduce why I'm going to give such type of lectures and online session or conference talks. Because I found recently everything get more competitive in the industry and in the education system. Okay. So students or other math enthusiasm, they will find the things they learned before probably is not enough, not good enough for them to understand the hard problems or practically speaking get them into elite schools or programs because they need to deal with harder problems to pass the selection process. And there are many problems will be available in all kinds of online resources and summer school problem across the world. Some of them are really challenging and selective. For example, like AIME Promise and SMAC are very popular programs that students all over the world are very interested in, including Wolfram summer school. So there are many harder problems they want to solve. And eventually you will get, for example, like Amy, you need to get a top 2.5% to be top 2.5% in the AMC 10 to be selected as student that you can participate Amy. And after that you will be need to complete lots of hard problems so that you will be elected for usmo. Okay, so for those hard problems, including like SMAC problems and the background you can check with Wolfram language using Wikipedia data and you will find the background of these programs and they always give you very challenging and interesting problem to solve. So this, when you actually in the exam, you are like exam takers and you can only do with a pencil, eraser, ruler and compasses, just like what mathematician does for 2,000 years ago. But I mean if you can solve that with those rudimentary methods, that'd be great. But for lots of people I feel like even the solution is just very hard to understand if you don't have any technology to support you. And this, this is basically the purpose of this type of session. I'm Making right now. Because with the Wolfram technology you can easily visualize because I'm a visual learner and visualization grade helps you to understand the problem. The other thing is those programs like to give you problems from combinatorics. Number theory or discrete calculus is basically pioneered by Knuth and he talks about lots of computer science related discrete calculus, discrete mathematics like computatorics. But what's the difference is discrete calculus requires you to do some calculus related things, which I mean in higher math it's take the limit or you do things about asymptotics which is covered greatly in the Wolfram language after version 12 and we have algebra and analysis for things that you can model by differential equation basically. And then if you work with those problems and typically you read the solutions, one of the biggest problem is you don't know where the solution come from. Because they usually prove either by contradiction or using constructive method to create a solution. This solution usually looks like comes from nowhere. I think using software typically Wolfram language greatly helps you to understand where these problems and typically solutions come from. For example, in one of the community article I just released, it's talking about a single problem but involves derangement pigeonhole principle, modular arithmetics or modular arithmetics and cyclic permutations. It's something like you. It's a baby course in group theory, okay. But these ideas and concepts are really abstract. If you don't do any simulation or experiment to help you understand what's behind it. You need to also throw in a bunch of parameters that you can change so that you can see how these parameters change the solution and how it affects our solution seeking process. So I would like to just give you some of the examples during this, during this talk. And these problems are selected from usually these very elite resources. So you can try to understand and read the code and play around with the problems and learn how you can come up with the solution by yourself. And this is very important because math I think is just like engineering or other experimental science to some point. Logic and the sort of deduction is just not enough. So you need to work with some of the cases typically with number theory, combinatorics and you know, this branches of mathematics. It's really hard to find a systematic way to to solve all the problems. You just need to play around some of the simple cases and eventually you know what to do and probably you find us result. And then you can link it to some online resources, someone maybe already solved it. But it's just very difficult if you just want to Describe them verbally. I'm going to show one of the problem like that in the, in the session. Okay, so here are my previous talks. These all have YouTube links, so you can click that or you can just check that it's here. So if you have the notebook, you just click that and you will be able to review the past problem solving sessions on YouTube. Okay. Okay. Now let's first start with. Without further ado, let's start from a very fresh me problem this year. So let me just quickly explain what's going on here. So there are five men and nine women sitting equally spaced around a circle in random order. So that means you have to sit on the the points or the vertices of a regular point polygon. So for example, the four people you must sit on a square. Okay, Five people you sit on the vertices, vertices of a pentagon. So you always that's equally spaced means on the circle. So the probability. So basically we are going to find the probability where every man sits diametrically opposite to a woman. Okay, the last part is basically the style of Amy. So you need to find a solution that's between.000 to 999. You have to write three digits. So this is the type of the format of an answer that's required in Amy. But eventually the problem just ask about the probability that every man sits diametrically opposite to a woman. Okay, let's see the simulation here. So assume men's are. Men are red, ladies are blue. So these are the simulated results. Okay. And this is also contribute this. After you learn this, how you program this problem, it'll give you a huge boost in Wolfram language programming skill. Because this is related to a very typical problem is generate random permutation with restrictions. So without the restriction you basically just randomly permute the dots on. On the circle. Okay, but my requirement is you can have blue to blue. Say you get one, eight is a blue to blue is diametric. Okay. But you cannot have red to red. The red must opposite to a blue point. Okay? So there is a. No, no red to red. Okay. So that's the constraint. So you need to find the correct probability that generate this type of permutation. And we want to generate this type of permutation efficiently because the worst method in this type of permutation generation is by rejection. You know, because some of the like the likelihood of a certain type of occurrence is very slim. So if you generate all the permutation, which usually is N factorial, that's going to just eat up your RAM very Quickly so it's not even possible to generate everything. So you want to generate things just without rejection. So you want your algorithm always generate the proper thing. But you can add some randomness because there are multiple, multiple cases that satisfying the solution at the same time. So of course you can find the AOPS link on this problem. It's Amy problem. Everything is document on that. But we were going to show you how you program that in Wolfram language very soon. Okay, so let's just work on the random constrained permutation first. Let's assume there's 14 people on it. You always need, they always need a even number. Because for example, you take five people, like you put them on a regular pentagon. Well, there's no people sitting diametrically, okay? Because you connect two vertices of a regular pentagon and none of them are going to pass the center of the circle. So you also have even number. And we generate all the members. So 1, 2, 3, 4, 5 to 14. And the key here is we need to first put seven people, put people in the seven diametric brackets. Before you put people on the seat, because we know the proper seating is paired by a diametric thing. So you basically generate the, the diametric brackets first. Okay, so one, if men, if someone men sit in one, eight must be a lady. So one lady. So it's red point, blue point or red point, blue point. Okay? So these are the brackets that. Because in that way if you select five brackets out of seven, you always guarantee that there is only one man sitting in one bracket. And here is a quick comment about this problem. You can't have like more than half of the people are male because by pigeonhole principle, if you say you have eight people, eight men, but you only have seven brackets. So guarantee there are at least one bracket with two red points or two males. So that will be zero probability. Okay? You won't have anything like that happen properly, untribully. So you always need let be have less than half of the population is male. And then you select 5 of 7 brackets above. So what I see. And randomly choose one of the binary seating position. Because binary seating, you can either choose 1 or 8, 2 or 9. So you choose a bracket and find the proper, whether it's one or two or one or eight. So you do that. And once you put five minutes in the brackets for all the women, you can just let them sit randomly. So that's the selection process. And then this thing comes to the visualization. You create a diametric link. So these links are just the dash Lines in our graph, okay. And you link them and that's. There you go. Then you have graphics. So I probably need to increase the font. This give you a proper seat arrangement for the problem. Okay. This one will generate the proper seating. And this is very important because as we progress we'll see that the probability is very low for this type of seating to be available as the whole population grows up. So you always want to use something like this to generate the brackets first. So you guarantee always you generate a random permutation that satisfy the proper seatings. And then let's just create the diagram we see here. You just wrap up all the code, just copy everything we had before and then put them in the table. So put them in a random function. So we can just generate rand whole things multiple times. So these are the 16 seats that's randomly generated. So we can have all the random permutations satisfy the diametric seating requirement. Okay. They all satisfied. Okay. There's no waste. I don't have anything to reject. So this is the most efficient algorithm to generate because you know, nothing's got wasted. So this would generate very efficiently for even very large seating with like 400 people sit there. You can just do that without, you know, eat up all the rams in your computer. So it also works fine with the most, I think the most mainstream type of laptops. You have like 16 gigabytes RAM, 500 gigabytes of SSD and i7 or i5 8th gen. It's just, even for enormous numbers, this algorithm generate permutation with such a requirement on the fly. Okay, so that's everything. We wrap it up before the Amy problem because they just ask you about 15 or like small numbers. But we can go a little bit further to see how this problems evolves. If we have lots of people, like 10,000 people, you know what's going on, what's going to be the, the property that we are going to observe for really large input. So let's see. Say if we have 2N people and Lambda and man lambda is the parameter. Because the, the most thing we have, for example is the, the worst case we have is 100 men and 100 women. Okay. So it's fine to have one man and 199 woman. Okay, because that will always give you the red blue requirement we have in the, in the problem. But the, so as N goes to very large the, the maximum proportion of a man is n. You know, 1n over 2n is 50%. So that's why I choose the parameter. Looks like this, it's 2N and Lambda N. And the lambda is to make sure the man is strict less than half of the group. Okay, that's what we do here. So let's see the parameters, how the symptomatic things behaviors. If we change. If we let N goes to infinity and have lambda here. Okay. Okay. So this gives you the asymptotic expression of the probability to have the required seating style. And let's simplify that. So this is the result. And let's see. So once you have asymptotics, you want to basically check that if the asymptotic expression gives you the same result as the as the brute force or direct computation. This is very important because for some of the problems like a typical incoming torque. So for example, if you want to compute N factorial, you know, given 10,000, so 1 times 2 times 3 times you go times 10,000. That's a really large number. Usually your computer cannot handle that. Even Mathematica can do that sometime. But if you do that intensive computation, it just costs too much time and you will always get overflow. If you want to do direct computation for computing torics with a large number. But I still want to know the behavior of inflectoria if it goes really large. So I will kick in you use asymptotics to find a sterling number for that you can check on Wikipedia, it's very well known. It will give you a very simple expression to show the behavior inflectorial. And we do same thing here, but for binomials and exponentials and binomials. So it will give you various a simple expression to compute that. Okay, so let's see, for example, let's fix n to 100 people and change lambda. So let's see how lambda. So this means like only 5% of the 5% divided by 2, that's 2.5% of people are male. These are like slightly close to 50% of people of the population are male. And if we increase N, if you fix N, we can see that as we increase the number population of the male, the probability to generate the required seating style is vanishing very quickly. I need to just make it a little larger. You can see somehow it's tiny here, but you can see that the number is 10 to the minus of 15. So this on log plot. So this is means if you have, let's say for example, 40% of 0.8 means that means 40%, you divide the two, they're less than 10 to the minus 10 to the power of negative 10 probability that you will need to find proper seeking. So it's just really not possible to do a direct computation and enumerate everything. But we can compare the result, the curve, with that from the direct computation. They look almost the same. You check on 0.8, it's still much less than 10 to the power negative 10. So they match very well. So let's just increase a little more. So if we, if we just do some special cases. So if we have like 50. 50% of people are male. So what's the result? Well, you get a much nicer, much nicer expression for that case. So this is as, for example, if you have 100 people or you have like 10,000 people, and what's the probability that you find a seating with, you know, diametrically constrained with 50% of male. So and you take like five times, you immediately can tell this thing is on the magnitude 2 to the power, but minus 5,000. Okay, you don't need to do any computation here, but you just plug in the number and it's you. Because that number is so tiny, you just take the logarithm of that to get the feeling of that number. So this number again decays very, very quickly. So here's the difference between this graph and the previous one. So this one is the fixing number. But change the proportion of male and females. Okay, so this thing is fixed proportion. So like 50%, but the change in the number of population n because it's 2M. Okay, so it's just uniquely determined by N. Okay, so we've specified the number of males. So the whole population is doubling that. So this is the result. And what's more important here is not about the actual expression here. You know, it really doesn't mean that much to me. But the thing is, it tells you that the proportion, the likelihood of such seating changes not only with respect to the proportion of man and woman, but also depends on the whole population. Okay, that's not something they asked during Amy problem. Once we do that, we would see this thing. Actually, that's the key to understand the problem. Okay, so this also shows you. This part shows you that as N increases, the estimate from our asymptotic behavior is very close to the direct computation. It's 8 over 10,000. Okay. Okay. So if this is also another special. Another special case is if you have a quarter of the group are male. So this is what you do. And you can have this expression. You simplify that and then you, you have that. And then if you go do More and more you will find a very interesting expression is just 2 to the power of negative 5, 3 to the power of 3. And if you do that, you have more such things. But eventually you will find this thing is always less than zero. So this gives you the idea that eventually you will have something like some power to the power N, some number to the power N. And this number is something generated by this which is less than 1 because that's the logarithm of that number. It's negative. So it means that number is less than 1. That number determines the regardless of what you kind of parameters you set for this, for this problem, it always decays. It always decays very fast like exponential. So and this gives you idea and. But the different N of lambda will give you different decaying rates. So that's the key of asymptotic analysis in this problem. Okay, and then I have some. This is like something like a half lifetime half life decay for this problem. What's the 50% chance for diametric seating if we have 200 people or 10,000 people? So for 200 people, let's just enumerate everything here. You will see that if we have 16 of them are male, we will have close to 50% of chance that you can generate the diametric CT. If we increase to 1000, the proportion of men must reduce to 2.7%. So that's the meaning of this calculation here. So with this software you can do many interesting things to explore much more deep behind the problem. Okay, so that's I think a problem one. We will split these things to many couple sessions because I want to just let you understand very deep things about the problem and just let me quickly look at the the chat. Okay. Okay. I'm glad you like it. Hey, let's move to the second problems because most of the problems are independent. So once we fit if we can split easily to multiple such live R and D sessions. If we don't have enough time to cover everything and you have the notebook or after the session and also some of the notebook I was post on just separate them and put on individual blogs on Warframe community. Just you have seen like this, it's published yesterday so it's a nice one to read. It's such a simple problem that covers very diversity topics in company topics. It's just a great thing to have Warframe language visualization tools. I just designed that diagram with some of the Wolfram function repository function to make the very nice and informative thing to show what's behind this sort of puzzle, what's the solution? What's the idea behind the solution on the puzzle? Okay, so let's start with the second problem. It's a problem from Promise, but you know, because Internet is so, so big, okay. And social media like AOPS and even on TikTok, people start to share math problem solving. So you easily have duplicates. So if you see enough, you probably will encounter the same problem in different competition or different selection sections. So this is a very interesting problem from Primus 2023 and the Bangladesh MO 2001. I saw that first on Michael Pence channel. He talked about that. I think it's a fun problem. And if you also search repeating integers on MSE Mathematica Stack Exchange, you will see this problem as well. But we will give you a general way to generate sufficient condition to generate lots of ridiculous things. Okay, so, so how many positive integers can you find? Okay, they're actually infinity, but we pretend we don't know the solution yet. So what I've said is discrete or number theory stuff. You always do that by testing the numbers. Okay, you do that by 2023. 2023. Of course this function is not necessary. I just find out MSE in case I need it. But line, it's. I can skip that in the problem. So it means. But. But just give you a good name, you know. Perfect square cube. Is it a perfect square Q? It's not. Okay, you, you do that. You just take the square root. It's not integer. That's. That means it's not. Okay, so what, what the, the equal means here is quite obvious. You just repeat the number in the connected. You go 111 is a 11 equal number. Okay? 1, 122 is. You have 2, 2. Okay. So you generate all the two digit stuff. So of course just like the previous problem, we, we only need a. Oh. Someone asked the best way to learn wolf language for solving math problem. Just follow this channel. I think I, I actually answered like 300 problems on AOPS before with the Wolfram language. So if you're lucky to find me. So you will see you can start from reading those solutions. So this gives you, you know, it's kind of silly and I just repeat this number in the previous number. We will say that the number of the population must be even the same case here because you duplicate a number. All right, so you must have even digits. You must have even digits. Okay? 1, 1, 2, 2, 3, 3, 4, 4, 8, 8, 9. 9. Okay. And then you, you do that for 10. Like this is four digits. Okay, four digits, four digits. 1 0, 1 0, 1 1, 1 2, 1 2, 1 3, 1 3, 1 4, 1 4. Okay, so you test everything. Okay, the easy way to do that is just. Let me just define this one again. Here we go. The union false. Okay. If you have anything like true, it will just give you true. So everything is false. Just you union all the solutions. You find the union of all the solutions and it is false. Okay, so it's false. Okay, so which means it's not possible to do that with such type of thing. If you are exam takers, you know, it's not possible for you to test 999 to like even 10,000 number. Let's do that again for even more because Mathematica Wolfman can handle more numbers. So 100, 100. That's six digits. Okay, six digits. You do that. It's false again. So now them are false. Now look at them give you perfectly square. And then you, you, you do that. And if you conclude that that thing, if you conclude, you know, you test a million number and then are right. You know, if you feel like, well, it's probably nothing exists, but very obviously that if you plug this numbers in, if you plug this number in the calculator, you repeat that number and take the square root of that number. So let me just show you how to type this number. Command C, You delete it. Copy, copy. It is integer. You see, this shows you this number is a perfect square. And if you don't believe me, you can just take this, let this guy times itself. See, this is the exact number you have. You can just compare that and digit by digit. And this is the number obviously. So yeah, at least you can find one. It's quite obvious because you can test it directly from the calculator. Okay, so let's see how you find this number. There are a couple steps because first is that you need to generate some numbers. And I'll just find some numbers that probably would be candidate. But by looking at the way I generated this number. So it's I times by one. Okay, so if you do that incrementally, you know, by checking like this number and by 102 or something like that, you probably won't get have enough time to find it in your lifetime. So we will need some smarter way to do that is we factor this number. We factor this number. The key is if you have say this number, okay, for four digits. This is four digits. It's AB times 101. So you must have 101 is a factor of AB, which is not possible here, okay? Because you want this number to be perfectly squared. So 101 is a prime number. You need a 101 in AB for it to work. Okay? So what if 1, something 0, 1 is not square is not a prime. So, for example, these are guys are not. Not primes. Are not primes. You know, you can, you can find a factorization for that, okay, but none of them work. You, you can just test it. The issue is that everything above this guy and number 11 before this guy, you always have factors, prime factors with at most power equal to one. So that's the tricky part. So the, the idea here is if you want to generate a thing that can be perfectly square as you repeat part of that, for example, in. With this guy. So this is this guy, you need some factors to be, have even power, even power. Because this guy won't affect the perfect squareness of this number. For example, you have 16, you divide by four. Four is perfectly square. So four left is also perfectly square, right? So you get rid of a perfect square. That should be fine. And then you need, you have these things. And because this thing, when you multiply together, will have less digits than this number. So it is possible for the product of this number as a factor of this guy. Okay? So this is how we find it. And then you take that thing out and you, you keep all the factors here, okay? But these factors are not enough because if you only, if this number only have these factors, you can just multiply that thing out, you won't have 11 digits. So we need to put some numbers for that to make the 11 digits. So what we do here is we need to do some calculation and find the right one. Okay? Okay, so this number times seven squared is 11 digits. Okay? So you may ask why we don't, why don't we multiply anything like 12 to that number? Or maybe, for example, it's 48 to that number. Okay? Make sure this number times this number must be perfectly squared. So you have to. This, you have to keep this part and multiplicate a perfect square to have the proper candidate. Okay? That's, that's the idea. So if we choose seven here and multiply five here, five works. So let's just take it out this number and let times the 10 to the power 11 +1 and find if it's a perfect square, it is you. You just take a square root of this guy and that's the result. If. So this guy times this guy is a perfect Square okay, so, so you, which means you repeat this number, they repeat this number, I repeat this number and take a square root and you multiply it. With this guy is the square root. Integer, integer square root of the number. So can we make the code a little better? Yes, we can, because with this code we are not good enough to find this guy. This is way beyond the factor integer stuff in general. So we need to find a better way. So this step two is a better way to write the code. May just make it look, look fancier, but it won't handle that large number. It's a number theoretical function called Mobius Mu. I'm not going to explain too much here, but it's well, very well used in an electric number theory. It's basically test the square freeness of algorithms of a number. For example, love is will result in zero because 12 is a 2.2 times 2 times 3 you have a power 2, you have a power 2 of 2 of power 2. So it won't give you anything non trivial, but non trivial stuff. You have 15 is non trivial, 15 is 3 times 5. 3 times 5 is 13 and 1 5. It gives you 1. Let's see, 30 is nontrivial, 30 is 2 times 3 times 5. You have three distinct prime factors, so it gives you minus 1. So if you have all the number of prime factors you have minus. When you have even numbers, it gives you positive. If you happen to have anything like 2, 4 in the factor, it gives you zero. Okay? Anything like 25 is zero. Okay, so basically that's what it is. It sounds simple, but it's NP hard. There's no efficient way to do that. If you find that one, you get maybe fields medalist for that. Okay, so, so this guy gives a zero because we, we have, we have element to the power of two here. So expected. So basically it asks you, you need to find the things result zero. Okay, There is another function you can use is a square freeness q square 3q square 3q in Mathematica. So this basically does the same thing here. Let me run that again. So even C50 is really slow. So 11, 21, 33, 39. So 39 is a candidate. So this guy is candidate and you do the same thing because the 13 is 13 square is the square. So we find any perfect square for up to times the leftovers and give you. Oh my God, this is give you like 13, give you 30, 39 digits. So basically this is how you do that thing. So it's the same thing that's the number you can test it's perfectly square. For even larger numbers. For even larger numbers. Why the solution was obvious is because we use number theory stuff again here. So there is a interesting thing that you can check in the factorization is even though the number itself is really not that big, but you do have very large prime factors occurs very early because for example, there are a bunch of more prime factors. Let's see, 19, for example, is much less than this guy, but 19. Oh, 19. Okay, let's do a little bit more. 73. 70. 77. 37, for example, 37. I would say 37. You're not 73. Okay, 37. So much smaller one, but does not occur. The reason is this guy gives you very small number in terms of multiplicative order. Let's do make it in the graph. I'll say 10. Let's see what's the prime again? This guy. Yeah, it's 24. It's really small. So which means if you have 10 to the power of 24 models, you basically divide that number. It gives you one. Okay, the other question is when you know something like this have as a candidate with nine. So basically means that this thing is two. So what time when when it's going to be two. So that'll be a little bit more more difficult because that that number probably occur very late. So we have that this means 10 to the power of this guy. Oh, sorry. This should be minus one. Up. It's 12. Okay, so so when we have something like this with with this guy, which becomes two. So it contains the factor like this. Make it two. So let's do that square. Okay, it probably takes some time to find it. But that's the idea to find the integers that satisfy this condition. This is basically how you find some ridiculous number to handle that. So let me quickly explain the multiplicative order here used here. So in this case for 11. 11. Okay, let's do that. Minus one. So 10 to the 11. So this guy means 11 will work in this case. Element will work. So you have two. Okay. So it is basically let you to solve residual families that satisfy a certain condition. For instance, 10 to the power 10 mod this thing basically means what kind of number you can find for 10 to the power of X such that when the model 17 it is minus. So basically they need to ask you to find x. But there are multiple x like that. For example, if you say you have like a four, so give you the minus one. Okay, but of course 12 will make sense because that's minus one times minus one times minus one minus one to the power three. So you ask to find the minimum x that satisfy this condition. So let's take a look at it. This is like 8. Where 8 comes from is. You do that, okay? You take 10 to the power 0 to the power 1 and to the power 8 and eventually you will have this this guy. So why this is a minus 8? Because minus 1 occurs at 8th position of the list. The reason is much more difficult to is way beyond the. If you have like higher order of 17 like t to the power or more P ADIC numbers. I actually wrote a blog about that. So if you are interested you can read that it's how P adic number affects the our solution seeking process. So this is a basically gives you idea how you find the power over k. That works. So in, in this case is if we have 11 to the power of 2, it will give you 10 to the power 11 mod this guy equal to minus 1. So which means you have the. These guys always work why you have k times 22 not instead 11? Because 22 is 1. So 10 to the power 11 is minus 1. So 10 to the power over 22 is positive 1. So this guy times positive 1 won't affect its modular result from 11 to the power 2. The other thing I want to point out is if you sometimes you cannot find a multiplical order, it just give you something like this. Because for example 10 to the. You look for 10 to the power of 0 and 1 because you only have two options here, right? None of them will give you the. For example 10 divided by 2 just with modulus for example minus 1. So it's not possible because 10 is 2 times 5. Regardless of how you do that, it always gives you zero. You won't have a multiplicative inverse in this situation. So that's why the algorithm is very efficient to find the proper result. Because we directly look at the solution, the pattern of solution in a higher level. And these things are equivalent. Co prime, false and these are false, false, false and unevaluated. These three results are identical in my case. So the ridiculous number I'm looking for is just plug in k equal to 16. It gives you the result and you do that. You can just find the, the integer factors of that number and repeat it and do the test again. So you will have the, the result we have in the, in the list. Okay, that's, that's the equal of integers. Okay, let's, let's, let's. This is my Remark. Okay, so this is how you find the, the even larger number. Oh, okay. I use this one. It's a much smaller than the one causing problem. So this number works is also a good candidate. So if 10, you can find a modular multiplicative inverse of this guy and you plug this guy in here. This is a valid candidate not for the event, the solution, but it's a valid candidate for these guys because first you need to find these ones sum 01 things before you can move on to finding the solution. So this number is way beyond any I think any machine you can handle on earth. I mean the number of all the atoms in the universe combined comparing to this number is a joke. Okay, so there's no way but with the number theoretic number, the number of theoretical thinking we can confirm this number works. Okay, so this is the power of a number theory. Yeah. To understand this type of problem, probably you want to get familiar with modular arithmetics. First I think language give you very nice functions comprise and the GCD stuff everything. You can work with large numbers very easily. And this is the foundation of a cryptography. If we have another things scheduled, I, I think I'm just being fine to comfortable to talk about cryptography with the building functions and that'd be very nice to to show you the power of number theory in real life. Okay. The third problem is from Promise. It's a kind of long one because I think these things require not only you have good math capability, but you also have good reading capability and writing skills. Okay. So you need to present your solutions very nicely. So this problem is basically ask you, you have a list of train on the track and there's no overtaking. Okay. So for example, you have a slow train and the fast train moving from left to right. You're moving left to right. So one. Yeah. From left to right. Okay. So if the fast train is on the right, the slow train is on the right. A fast train is on the right and the slow train is on the left. Everything is travel to the right. You will have two chain of trains because the slow ones will never catch up with the fast one. But if you reverse the order, put the fast train on the left and the slow train on the right. So eventually there is going to be a collision. But the collision is it is not a real world collision because it won't cause any trouble. But the only consequence is the 2 train will travel at the same speed as the slow train. Okay, what I mean so let's see there if there are three equally Spaced trains that give you different speed. So for example, they travel at 1, 2, 3. So 1 is on the left, the 3 is on the right. So eventually you will have three trains. Okay, three chain of trains. So it's a one chain can be only with one element. So that's the eventual case. But if you have say 3, 3 2, 1. 3 2, 1. Okay, you travel to the right. So eventually you will have, you will have one chain. Because three hit two for example. And they all travel at two, two hit one. You eventually you hit everything becomes one. That's the slow train. But what about three 1, 3, 2, 13 2, 1, 32 is one is really slow on the left, but the three will catch up with the two. So you eventually you have two trains, two chain of trace. So they ask you what's the average of all possible orderings? You know? So basically if you have four trains, you have different permutations, right? And different permutations or different initial state determines the number of trains you have eventually. So let's see how we can solve this problem with. With the simulations, you know, I did not solve it at the beginning, but until. But once I have the code, I generate some cases and throw it into Wolfram Alpha community solution. So that, that. So even sometimes people preparing for this type of exams, they spend too much time on single problem. That's bad because for discrete calculus number theory, you want to see more problem as much as many as possible, you know. So don't spend too much time on that one problem. And it's reading solution is also very important, very important part of the learning process. And more importantly, understanding the solutions. Okay. And find the connections. And this problem gives you everything like that. So if you learn anything like programming, you know, for this type of problem, for very long chains, you want to break into sub problems. It's either divide a counter, divide, conquer. So it's like a recursion you solve. For example, you want to know Fibonacci number at nth place. You basically computed the two numbers before that and then two numbers before each of them. So this basically this divided conquer. Or you can do like a dynamic programming because it's not only divide and conquer, you also save the result from your previous problems. So eventually you don't need to do the sub problems again, again, again. So you can just use the result from them. So this problem is kind of similar. So if you try to do that for but because though they only ask you like 3, 4, 5, 7. But you know, if you are anyone like Interested in math, you easily think about how we do that for 10, 20 or even larger number of N. It's the nature of these math lovers. I think you have a program language like Wolfram language that really helps you to understand this very quickly. So the key is, the problem is what we can think about easily is if you have one on the rightmost side, so everything is going to be one chain because you know, even slower, some slightly faster train, you know, they collide together, they will be the like the slowest one. The slowest one is at least two. So you will have. So eventually everything will catch up to. If for example, you have something three in the middle, but three will catch up with one and everything becomes one and you have some, you know, leftovers, eventually they will come catch up again with the leftovers. Because the rightmost chain, because the rightmost chain would be the slowest one at speed of one. Okay, so it's quite obvious if one is on the right, eventually you have only one chain. Okay, that's the extreme case. But how can we extrapolate the extreme case to the leftovers? You know, could do more cases. So we think about it, you know, we have use level one, you know, so what about the others? Because if we get rid of the slow things about some of the part of the trains, the slowest one, the slowest training for the leftovers will be one, because it's quite obvious. So that gives you idea about the induction. So if we extrapolated, the thinking is it's not about the actual point, the actual number of one, it's about the, the slowest number, the smallest number for any leftover train and it's one. Okay, it's the new one because. Because this is. If we talk about like abstract ideas, it's like accountable set, you know, lip finding in the countable center, you always have the minimum value. And that minimum value will automatically becomes one if you take the slow trains out. Okay, so that gives idea to create a very simple program. It's not necessarily the code golf thing, but I think it's just simple enough to give you an idea what's going on here. So the key is if we have amp train, we have zero train as zero chain. And sometimes we also have one chain. So one chain. For example, if we have every number available, say like 1, 2, 3, 4, if one is to the right, then you will have one chain. Okay, but what if one is not available? What if one one is not available. Here is, you need something like one. So what is one for something like 2, 4, 3, 5. So two is one. Okay. So two is one. It must be on the right most hand side. Then it's the slowest one. Then you eventually have one chain. So that. That what it means is if you have the minimum number on the rightmost hand side of the list, you have one chain. Okay. And then we do recursive thing is we to. We need to find where the smallest number in the list and that number will break the chain into two parts. One is something like for example if we have 6, 4 1, 3, 5. Let's. Let's just write it down. 6, 4, 1, 2, 3. Okay. One is in the middle. So this guy would be something like one chain or something. Right. And this will be another thing. Okay. And then you call again because this guy is the smallest number it's on left and it break into two chains. So eventually you have one. So basically it turns to 1, 2, 3 and eventually you have three chains of trains. And then you do that. You can just use the code to do some test it generate cases for simple cases quickly. And what if we do three case for 10 numbers it'll give you three chains. So this guy would be one chain and this guy would be one chain because nine hit three will be three and five catch up with three becomes three and this guy is everything eventually becomes one. So this is one chain and two is itself. And this is one chain. So eventually you have three. We can also work on really large numbers. And like I found it will give you some numbers. You can. You can just quickly check that and then how to find the averages. I just do brute force for small numbers. But hold on. Oh, okay. Let me just. Pause that. Define everything first clear. It's going to give you some smaller numbers. Rest and give us idea. That's the. That's the distribution of the number. It doesn't look very. It gives us a general idea about how the number behaviors, but it does not give you the actual solution for that. Let's see Rest is. Look at rest. Okay. Oh, that's all the result here. Let's just do that again. For the permutations. For all the permutations for one train, two train, three trains, three train, four train and six trains together. Okay. Then you have a number, a list of numbers and that's all the sort of the possible outcomes. The outcomes. And I just ask a number, throw it online and I find it's this number. So ask what for mouth. I did exactly the same. It's this number either on OEIS or Wolfram Alpha will give using the same idea give you idea. And what I mean is for connections is if you have happen to find this number is a famous number, then you're good to go. Because this number you will find tons of literatures about that on OEIS or math world. So it will show you why this number works, why this number generate is associated to our train counting problems. So if you, you know, because there are. The certain number here is not that general. It's required this guy to be two. You, you use the, the parameter, set it to two, it will give you the proper result. So 1, 3, 115274 and 1764 and so on. And it happens to be the N factorial times harmonic number. So the average number is. This number divides the harmonic stuff divides N factorial. So what you left is harmonic number. So that's the average of the length of the train. You can, you can do that. That is it should be the same thing as our result. You can 761-over 28761 over 284 for eight trains. So this will give you the solution for that. And what's more importantly here is the average is actually diverges because this is a well known property of harmonic numbers. It diverges very slowly at the rate of a login. But it diverges. So that's something you can learn from. You can immediately point out for the problems and then just. I said if you happen to find this is a famous number then you have infinity resources to learn the connection of steering numbers, harmonic numbers and the number of trains we are counting that. So yeah, I think you know help if you just do that by hand. I think it's pretty time consuming to find anything useful. And even if I, I have like a number like this, you know, it's not a arithmetic progression or it's not a simple like a power or geometric. Geometric result, geometrical progression. You know, I, I think I probably have hard time to find out what's the number going. I'm not Euler or Lagrange. So I, I need some, some technology to help me. So eventually I, I find out that this is the, the. The result we are looking for. So yeah, you can find the, the link from oeis you just google it or you use Math World to find terms of reference about why this number work. And typically I think this relates to this problem because this time this stony number S is originally associated with the number of distinct. I mean partition of in partition of cycles in a chain of integers. So that makes it sound like very close to our train problems. So, yeah, I think that's. That's it. We wish. I still have a couple more problems, but I think it would be good if we, you know, take a break today and talk about in the next part of the problem solving session. And hopefully you learned something very useful today and see you next time. Bye. Bye.
More from Guy
Cheryl Strauss Einhorn | The Human Edge: Smarter Decisions in the Age of AI | Talks at Google
Rachel Glennerster | Innovation and the Center for Global Development | Talks at Google
Rebecca Winthrop | Rethinking the Purpose of Education in the Age of AI | Talks at Google
Dr. Robert Wachter | A Giant Leap: How AI Is Transforming Healthcare... | Talks at Google
