Author: IMC

It seems obvious. You arrive at the checkouts and see one queue is much longer than the other, so you join the shorter one. But, before long, the people in the bigger line zoom past you and you’ve barely moved towards the exit.

When it comes to queuing, the intuitive choice is often not the fastest one. Why do queues feel like they slow down as soon as you join them? And is there a way to decide beforehand which line is really the best one to join? Mathematicians have been studying these questions for years. So can they help us spend less time waiting in line?

The intuitive strategy seems to be to join the shortest queue. After all, a short queue could indicate it has an efficient server, and a long queue could imply it has an inexperienced server or customers who need a lot of time. But generally this isn’t true.

Without the right information, it could even be disadvantageous to join the shortest queue. For example, if the short queue at the supermarket has two very full trolleys and the long queue has four relatively empty baskets, many people would actually join the longer queue. If the servers are equally efficient, the important quantity here is the number of total items in the queue, not the number of customers. But if the trolleys weren’t very full but the hand baskets were, it wouldn’t be so easy to estimate and the choice wouldn’t be so clear.

This simple example introduces the concept of service time distribution. This is a random variable that measures how long it will take a customer to be served. It contains information about the average (mean) service time and about the standard deviation from the mean, which represents how the service time fluctuates depending on how long different customers need.

The other important variable is how often customers join the queue (the arrival rate). This depends on the average amount of time that passes between two consecutive customers entering the shop. The more people that arrive to use a service at a specific time, the longer the queues will be.

Never mind the queue, I picked the wrong shop. Shutterstock

Depending on what these variables are, the shortest queue might be the best one to join – or it might not. For example, in a fish and chip shop you might have two servers both taking orders and accepting money. Then it is most often better to join the shortest queue since the time the servers’ tasks take doesn’t vary much.

Unfortunately, in practice, it’s hard to know exactly what the relevant variables are when you enter a shop. So you can still only guess what the fastest queue to join will be, or rely on tricks of human psychology, such as joining the leftmost queue because most right-handed people automatically turn right.

Did you get it right?

Once you’re in the queue, you’ll want to know whether you made the right choice. For example, is your server the fastest? It is easy to observe the actual queue length and you can try to compare it to the average. This is directly related to the mean and standard deviation of the service time via something called the Pollaczek-Khinchine formula, first established in 1930. This also uses the mean inter-arrival time between customers.

Unfortunately, if you try to measure the time the first person in the queue takes to get served, you’ll likely end up feeling like you chose the wrong line. This is known as Feller’s paradox or the inspection paradox. Technically, this isn’t an actual logical paradox but it does go against our intuition. If you start measuring the time between customers when you join a queue, it is more likely that the first customer you see will take longer than average to be served. This will make you feel like you were unlucky and chose the wrong queue.

The inspection paradox works like this: suppose a bank offers two services. One service takes either zero or five minutes, with equal probability. The other service takes either ten or 20 minutes, again with equal probability. It is equally likely for a customer to choose either service and so the bank’s average service time is 8.75 minutes.

If you join the queue when a customer is in the middle of being served then their service can’t take zero minutes. They must be using either the five, ten or 20 minute service. This pushes the time that customer will take to be served to more than 11 minutes on average, more than the true average for the of 8.75 minutes. In fact, two out of three times you encounter the same situation, the customer will want either the 10 or 20 minute service. This will make it seem like the line is moving more slowly than it should, all because a customer is already there and you have extra information.

So while you can use maths to try to determine the fastest queue, in the absence of accurate data – and for your own peace of mind – you’re often better just taking a gamble and not looking at the other options once you’ve made your mind up.

For more insights like this, visit our website at www.international-maths-challenge.com.
Credit of the article given to Enrico Scalas, Nicos Georgiou

SeventyFour via Shutterstock

Prime numbers are more than just numbers that can only be divided by themselves and one. They are a mathematical mystery, the secrets of which mathematicians have been trying to uncover ever since Euclid proved that they have no end.

An ongoing project – the Great Internet Mersenne Prime Search – which aims to discover more and more primes of a particularly rare kind, has recently resulted in the discovery of the largest prime number known to date. Stretching to 23,249,425 digits, it is so large that it would easily fill 9,000 book pages. By comparison, the number of atoms in the entire observable universe is estimated to have no more than 100 digits.

The number, simply written as 2⁷⁷²³²⁹¹⁷-1 (two to the power of 77,232,917, minus one) was found by a volunteer who had dedicated 14 years of computing time to the endeavour.

You may be wondering, if the number stretches to more than 23m digits, why we need to know about it? Surely the most important numbers are the ones that we can use to quantify our world? That’s not the case. We need to know about the properties of different numbers so that we can not only keep developing the technology we rely on, but also keep it secure.

Secrecy with prime numbers

One of the most widely used applications of prime numbers in computing is the RSA encryption system. In 1978, Ron Rivest, Adi Shamir and Leonard Adleman combined some simple, known facts about numbers to create RSA. The system they developed allows for the secure transmission of information – such as credit card numbers – online.

The first ingredient required for the algorithm are two large prime numbers. The larger the numbers, the safer the encryption. The counting numbers one, two, three, four, and so on – also called the natural numbers – are, obviously, extremely useful here. But the prime numbers are the building blocks of all natural numbers and so even more important.

 

Take the number 70 for example. Division shows that it is the product of two and 35. Further, 35 is the product of five and seven. So 70 is the product of three smaller numbers: two, five, and seven. This is the end of the road for 70, since none of these can be further broken down. We have found the primal components that make up 70, giving its prime factorisation.

Multiplying two numbers, even if very large, is perhaps tedious but a straightforward task. Finding prime factorisation, on the other hand, is extremely hard, and that is precisely what the RSA system takes advantage of.

Suppose that Alice and Bob wish to communicate secretly over the internet. They require an encryption system. If they first meet in person, they can devise a method for encryption and decryption that only they will know, but if the initial communication is online, they need to first openly communicate the encryption system itself – a risky business.

However, if Alice chooses two large prime numbers, computes their product, and communicates this openly, finding out what her original prime numbers were will be a very difficult task, as only she knows the factors.

So Alice communicates her product to Bob, keeping her factors secret. Bob uses the product to encrypt his message to Alice, which can only be decrypted using the factors that she knows. If Eve is eavesdropping, she cannot decipher Bob’s message unless she acquires Alice’s factors, which were never communicated. If Eve tries to break the product down into its prime factors – even using the fastest supercomputer – no known algorithm exists that can accomplish that before the sun will explode.

The primal quest

Large prime numbers are used prominently in other cryptosystems too. The faster computers get, the larger the numbers they can crack. For modern applications, prime numbers measuring hundreds of digits suffice. These numbers are minuscule in comparison to the giant recently discovered. In fact, the new prime is so large that – at present – no conceivable technological advancement in computing speed could lead to a need to use it for cryptographic safety. It is even likely that the risks posed by the looming quantum computers wouldn’t need such monster numbers to be made safe.

It is neither safer cryptosystems nor improving computers that drove the latest Mersenne discovery, however. It is mathematicians’ need to uncover the jewels inside the chest labelled “prime numbers” that fuels the ongoing quest. This is a primal desire that starts with counting one, two, three, and drives us to the frontiers of research. The fact that online commerce has been revolutionised is almost an accident.

The celebrated British mathematician Godfrey Harold Hardy said: “Pure mathematics is on the whole distinctly more useful than applied. For what is useful above all is technique, and mathematical technique is taught mainly through pure mathematics”. Whether or not huge prime numbers, such as the 50th known Mersenne prime with its millions of digits, will ever be found useful is, at least to Hardy, an irrelevant question. The merit of knowing these numbers lies in quenching the human race’s intellectual thirst that started with Euclid’s proof of the infinitude of primes and still goes on today.

For more insights like this, visit our website at www.international-maths-challenge.com.
Credit of the article given to Ittay Weiss

Credit: Peter Dazeley Getty Images

Not getting a flu shot could endanger more than just one’s own health, herd immunity calculations show   

As the annual flu season approaches, medical professionals are again encouraging people to get flu shots. Perhaps you are among those who rationalize skipping the shot on the grounds that “I never get the flu” or “if I get sick, I get sick” or “I’m healthy, so I’ll get over it.” What you might not realize is that these vaccination campaigns for flu and other diseases are about much more than your health. They’re about achieving a collective resistance to disease that goes beyond individual well-being—and that is governed by mathematical principles unforgiving of unwise individual choices.

When talking about vaccination and disease control, health authorities often invoke “herd immunity.” This term refers to the level of immunity in a population that’s needed to prevent an outbreak from happening. Low levels of herd immunity are often associated with epidemics, such as the measles outbreak in 2014-2015 that was traced to exposures at Disneyland in California. A study investigating cases from that outbreak demonstrated that measles vaccination rates in the exposed population may have been as low as 50 percent. This number was far below the threshold needed for herd immunity to measles, and it put the population at risk of disease.

The necessary level of immunity in the population isn’t the same for every disease. For measles, a very high level of immunity needs to be maintained to prevent its transmission because the measles virus is possibly the most contagious known organism. If people infected with measles enter a population with no existing immunity to it, they will on average each infect 12 to 18 others. Each of those infections will in turn cause 12 to 18 more, and so on until the number of individuals who are susceptible to the virus but haven’t caught it yet is down to almost zero. The number of people infected by each contagious individual is known as the “basic reproduction number” of a particular microbe (abbreviated R0), and it varies widely among germs. The calculated R0 of the West African Ebola outbreak was found to be around 2 in a 2014 publication, similar to the R0computed for the 1918 influenza pandemic based on historical data.

If the Ebola virus’s R0 sounds surprisingly low to you, that’s probably because you have been misled by the often hysterical reporting about the disease. The reality is that the virus is highly infectious only in the late stages of the disease, when people are extremely ill with it. The ones most likely to be infected by an Ebola patient are caregivers, doctors, nurses and burial workers—because they are the ones most likely to be present when the patients are “hottest” and most likely to transmit the disease. The scenario of an infectious Ebola patient boarding an aircraft and passing on the disease to other passengers is extremely unlikely because an infectious patient would be too sick to fly. In fact, we know of cases of travelers who were incubating Ebola virus while flying, and they produced no secondary cases during those flights.

Note that the R0 isn’t related to how severe an infection is, but to how efficiently it spreads. Ebola killed about 40 percent of those infected in West Africa, while the 1918 influenza epidemic had a case-fatality rate of about 2.5 percent. In contrast, polio and smallpox historically spread to about 5 to 7 people each, which puts them in the same range as the modern-day HIV virus and pertussis (the bacterium that causes whooping cough).

Determining the R0 of a particular microbe is a matter of more than academic interest. If you know how many secondary cases to expect from each infected person, you can figure out the level of herd immunity needed in the population to keep the microbe from spreading. This is calculated by taking the reciprocal of R0 and subtracting it from 1. For measles, with an R0 of 12 to 18, you need somewhere between 92 percent (1 – 1/12) and 95 percent (1 – 1/18) of the population to have effective immunity to keep the virus from spreading. For flu, it’s much lower—only around 50 percent. And yet we rarely attain even that level of immunity with vaccination.

Once we understand the concept of R0, so much about patterns of infectious disease makes sense. It explains, for example, why there are childhood diseases—infections that people usually encounter when young, and against which they often acquire lifelong immunity after the infections resolve. These infections include measles, mumps, rubella and (prior to its eradication) smallpox—all of which periodically swept through urban populations in the centuries prior to vaccination, usually affecting children.

Do these viruses have some unusual affinity for children? Before vaccination, did they just go away after each outbreak and only return to cities at approximately five- to 10-year intervals? Not usually. After a large outbreak, viruses linger in the population, but the level of herd immunity is high because most susceptible individuals have been infected and (if they survived) developed immunity. Consequently, the viruses spread slowly: In practice, their R0 is just slightly above 1. This is known as the “effective reproduction number”—the rate at which the microbe is actually transmitted in a population that includes both susceptible and non-susceptible individuals (in other words, a population where some immunity already exists). Meanwhile, new susceptible children are born into the population. Within a few years, the population of young children who have never been exposed to the disease dilutes the herd immunity in the population to a level below what’s needed to keep outbreaks from occurring. The virus can then spread more rapidly, resulting in another epidemic.

An understanding of the basic reproduction number also explains why diseases spread so rapidly in new populations: Because those hosts lack any immunity to the infection, the microbe can achieve its maximum R0. This is why diseases from invading Europeans spread so rapidly and widely among indigenous populations in the Americas and Hawaii during their first encounters. Having never been exposed to these microbes before, the non-European populations had no immunity to slow their spread.

If we further understand what constellation of factors contributes to an infection’s R0, we can begin to develop interventions to interrupt the transmission. One aspect of the R0 is the average number and frequency of contacts that an infected individual has with others susceptible to the infection. Outbreaks happen more frequently in large urban areas because individuals living in crowded cities have more opportunities to spread the infection: They are simply in contact with more people and have a higher likelihood of encountering someone who lacks immunity. To break this chain of transmission during an epidemic, health authorities can use interventions such as isolation (keeping infected individuals away from others) or even quarantine (keeping individuals who have been exposed to infectious individuals—but are not yet sick themselves—away from others).

Other factors that can affect the R0 involve both the host and the microbe. When an infected person has contact with someone who is susceptible, what is the likelihood that the microbe will be transmitted? Frequently, hosts can reduce the probability of transmission through their behaviors: by covering coughs or sneezes for diseases transmitted through the air, by washing their contaminated hands frequently, and by using condoms to contain the spread of sexually transmitted diseases.

These behavioral changes are important, but we know they’re far from perfect and not particularly efficient in the overall scheme of things. Take hand-washing, for example. We’ve known of its importance in preventing the spread of disease for 150 years. Yet studies have shown that hand-washing compliance even by health care professionals is astoundingly low — less than half of doctors and nurses wash their hands when they’re supposed to while caring for patients. It’s exceedingly difficult to get people to change their behavior, which is why public health campaigns built around convincing people to behave differently can sometimes be less effective than vaccination campaigns.

How long a person can actively spread the infection is another factor in the R0. Most infections can be transmitted for only a few days or weeks. Adults with influenza can spread the virus for about a week, for example. Some microbes can linger in the body and be transmitted for months or years. HIV is most infectious in the early stages when concentrations of the virus in the blood are very high, but even after those levels subside, the virus can be transmitted to new partners for many years. Interventions such as drug treatments can decrease the transmissibility of some of these organisms.

The microbes’ properties are also important. While hosts can purposely protect themselves, microbes don’t choose their traits. But over time, evolution can shape them in a manner that increases their chances of transmission, such as by enabling measles to linger longer in the air and allowing smallpox to survive longer in the environment.

By bringing together all these variables (size and dynamics of the host population, levels of immunity in the population, presence of interventions, microbial properties, and more), we can map and predict the spread of infections in a population using mathematical models. Sometimes these models can overestimate the spread of infection, as was the case with the models for the Ebola outbreak in 2014. One model predicted up to 1.4 million cases of Ebola by January 2015; in reality, the outbreak ended in 2016 with only 28,616 cases. On the other hand, models used to predict the transmission of cholera during an outbreak in Yemen have been more accurate.

The difference between the two? By the time the Ebola model was published, interventions to help control the outbreak were already under way. Campaigns had begun to raise awareness of how the virus was transmitted, and international aid had arrived, bringing in money, personnel and supplies to contain the epidemic. These interventions decreased the Ebola virus R0 primarily by isolating the infected and instituting safe burial practices, which reduced the number of susceptible contacts each case had. Shipments of gowns, gloves and soap that health care workers could use to protect themselves while treating patients reduced the chance that the virus would be transmitted. Eventually, those changes meant that the effective R0 fell below 1—and the epidemic ended. (Unfortunately, comparable levels of aid and interventions to stop cholera in Yemen have not been forthcoming.)

Catch-up vaccinations and the use of isolation and quarantine also likely helped to end the Disneyland measles epidemic, as well as a slightly earlier measles epidemic in Ohio. Knowing the factors that contribute to these outbreaks can aid us in stopping epidemics in their early stages. But to prevent them from happening in the first place, a population with a high level of immunity is, mathematically, our best bet for keeping disease at bay.

For more insights like this, visit our website at www.international-maths-challenge.com.

Credit of the article given to Tara C. Smith & Quanta Magazine

Sitting in a bar, you start chatting to a man who issues you a challenge. He hands you five red and two black cards. After shuffling, you lay them on the bar, face down. He bets you that you cannot turn over three red cards. And to help you, he explains the odds.

When you draw the first card, the odds are 5-2 (five red cards, two black cards) in favour of picking a red card. The second draw is 4-2 (or 2-1) and the third draw is 3-2. Each time you draw a card the odds appear to be in your favour, in that you have more chance of drawing a red card than a black card. So, do you accept the bet?

If you answered yes, perhaps it’s time for you to go over your maths. It’s a foolish bet. The odds given above are only for a perfect draw. The real odds of you being able to carry out this feat are actually 5-2 against you. That is, for every seven times you play, you’ll lose five times.

Odds against you

This type of bet is often called a proposition bet, which is defined as a wager on something that seems like a good idea, but for which the odds are actually against you, often very much against you, perhaps even making it impossible for you to win.

Let’s assume that you took the bet and, almost inevitably, lost money. But this is just for fun, right? So your new “friend” suggests a way that you can get your money back. He takes two more red cards and hands them to you, so you now have seven red cards and two black cards. You shuffle the nine cards and lay them out, face down, in a three by three grid. He bets you even money that you can’t pick out a straight line (vertical, horizontal or diagonal) that has only red cards.

Nine Card Hustle. Graham Kendall created image

Intuitively, this might sound like a better bet and the odds are actually evens if the two black cards are next to each other in a corner (see image). In total there are eight lines to choose from and four contain only red cards, and four contain a black card. But that is as good as it gets.

If the black cards are in opposite corners then you can only win by choosing the centre horizontal or vertical row so the odds are 6-2 (or 3-1) against you winning. Every other layout gives you three winning lines and five losing lines. This bet only has 12 ways of succeeding, against 22 ways of you losing. Hardly an even-chance bet.

Have another go

Try to evaluate the odds for this proposition bet.

You shuffle a pack of cards and cut it into three piles. You are offered even money that one of the cards on top of the piles will be a picture card (a jack, queen or king). That is, if a picture card shows up, you lose. Do you think this is a good bet?

One way of reasoning is that there are only 12 losing cards against 40 winning cards, so the odds look better than evens? But this is the wrong way of looking at it. It is really what’s known as a combinatorics problem. We should also realise that we are just choosing three cards at random.

There are 22,100 ways of choosing three cards from a 52 card deck. Of these, 12,220 will contain at least one picture card – so you lose – meaning that 9,880 will not contain a picture card – when you win. If you translate this to odds, you will lose fives times out of every nine times you play (5-4 against you). The even chance bet you have been offered is not the good value that you thought it was and you will lose money if you play a few times.

 

A Final Example

We can all agree that you have a 50/50 chance of guessing heads or tails in a coin toss. But if you toss the coin ten times, would you expect to see five heads and five tails? If you were offered odds of 2-1 to try this, would you take the bet? You’d be a sucker if you did.

Five heads and five tails will occur more often than any other combination, but there are many other ways that ten flips of a coin can land. In fact, the bet is 5-2 against you.

Another name for a proposition bet is the “sucker” bet, and there is no surprise who the sucker is. But don’t feel too bad. We are all generally very poor at evaluating true odds. A famous example is the Monty Hall Problem. Even mathematicians could not agree on the right answer to this seemingly simple problem.

We have focused on bets where it is difficult, especially when under the pressure of deciding whether to bet or not, to calculate the true odds. But there are many other proposition bets that do not rely on calculating odds. And there are many other sucker bets, with probably the most famous being the Three Card Monty.

If faced with this type of bet, what is the best thing you can do? I’d suggest you simply walk away.

For more insights like this, visit our website at www.international-maths-challenge.com.
Credit of the article given to Graham Kendall

Credit: OLENA SHMAHALO Quanta Magazine

Computer scientists have come up with an algorithm that can fairly divide a cake among any number of people

Two young computer scientists have figured out how to fairly divide cake among any number of people, setting to rest a problem mathematicians have struggled with for decades. Their work has startled many researchers who believed that such a fair-division protocol was probably impossible.

Cake-cutting is a metaphor for a wide range of real-world problems that involve dividing some continuous object, whether it’s cake or, say, a tract of land, among people who value its features differently—one person yearning for chocolate frosting, for example, while another has his eye on the buttercream flowers. People have known at least since biblical times that there’s a way to divide such an object between two people so that neither person envies the other: one person cuts the cake into two slices that she values equally, and the other person gets to choose her favorite slice. In the book of Genesis, Abraham (then known as Abram) and Lot used this “I cut, you choose” procedure to divide land, with Abraham deciding where to divide and Lot choosing between Jordan and Canaan.

Around 1960, mathematicians devised an algorithm that can produce a similarly “envy-free” cake division for three players. But until now, the best they had come up with for more than three players was a procedure created in 1995 by political scientist Steven Brams of New York University and mathematician Alan Taylor of Union College in Schenectady, New York, which is guaranteed to produce an envy-free division, but it is “unbounded,” meaning that it might need to run for a million steps, or a billion, or any large number, depending on the players’ cake preferences.

Brams and Taylor’s algorithm was hailed as a breakthrough at the time, but “the fact that it wasn’t bounded I think was a huge shortcoming,” said Ariel Procaccia, a computer scientist at Carnegie Mellon University and one of the creators of Spliddit, a free online tool that provides fair-division algorithms for tasks like dividing chores or rent among roommates.

Over the past 50 years, many mathematicians and computer scientists, including Procaccia, had convinced themselves that there was probably no bounded, envy-free algorithm for dividing cake among n players.

“This is the very problem that got me into the subject of fair division,” said Walter Stromquist, a mathematics professor at Bryn Mawr College in Pennsylvania who proved some of the seminal results on cake cutting in 1980. “I have thought all my life that I would come back to it when I had time and prove that this particular extension of the result was impossible.”

But in April, two computer scientists defied expectations by posting a paper online describing an envy-free cake-cutting algorithm whose running time depends only on the number of players, not on their individual preferences. One of the pair—27-year-old Simon Mackenzie, a postdoctoral researcher at Carnegie Mellon—will present the pair’s findings on Oct. 10 at the 57th annual IEEE Symposium on Foundations of Computer Science, one of computer science’s pre-eminent conferences.

The algorithm is extraordinarily complex: Dividing a cake among n players can require as many as n^n^n^n^n^n steps and a roughly equivalent number of cuts. Even for just a handful of players, this number is greater than the number of atoms in the universe. But the researchers already have ideas for making the algorithm much simpler and faster, said the other half of the team, Haris Aziz, a 35-year-old computer scientist at the University of New South Wales and Data61, a data research group in Australia.

For the people who study the theory of fair division, this is “definitely the biggest result in decades,” Procaccia said.

Pieces of Cake

Aziz and Mackenzie’s new algorithm builds on an elegant procedure that mathematicians John Selfridge and John Conway independently came up with around 1960 for dividing a cake among three people.

If Alice, Bob and Charlie want to share a cake, the algorithm starts by having Charlie cut the cake into three slices that are equally valuable from his perspective. Alice and Bob are each asked to point to their favorite slices, and if they like different slices, we’re done—they each take their favorite, Charlie takes the remaining slice, and everyone goes home happy.

If Alice and Bob have the same favorite, then Bob is asked to trim a little cake off that slice so that what remains is equal in value to his second-favorite slice; the trimmed bit is set aside for later. Now Alice gets to choose her favorite piece from among the three slices, and then Bob gets to choose, with the requirement that if Alice didn’t choose the trimmed slice, he must take it. Charlie gets the third slice.

At this stage, none of the players envy each other. Alice is happy since she got to choose first; Bob is happy since he got one of his two equally preferred top choices; and Charlie is happy because he got one of his three original pieces, all of which are equal in his eyes.

But there’s still the trimmed bit to be divided. What makes it possible to divide this bit without creating still more trimmings, and getting into an infinite cycle of trimming and choosing, is the fact that Charlie is more than merely satisfied with the cake he has gotten so far; he would not feel cheated even if the player with the trimmed slice gets all the cake that’s waiting to be allocated, since the trimmed slice plus the trimming equals one of the original slices. Aziz and Mackenzie describe this relationship by saying that Charlie “dominates” the player who got the trimmed slice.

Now if, for example, Alice was the one who got the trimmed slice, the algorithm proceeds as follows: Bob cuts the trimmings into three pieces that he values equally, and then first Alice gets to choose a piece, then Charlie, then Bob. Everyone is happy: Alice because she got to choose first, Charlie because he gets a slice he likes better than Bob’s (and he didn’t care how much Alice took), and Bob because the three slices are equal in his view.

Brams and Taylor used the notion of domination (without calling it that) in designing their 1995 algorithm, but they couldn’t push the idea far enough to get a bounded algorithm. For the next 20 years, neither could anyone else. “I don’t think it’s for lack of trying,” Procaccia said.

Rookie Cake-Cutters

When Aziz and Mackenzie decided to tackle the problem a couple of years ago, they were comparative newcomers to the cake-cutting problem. “We did not have as much background as people who have been intensely working on it would have,” Aziz said. “Although that is mostly a disadvantage, in this case it was somewhat of an advantage, because we were not thinking in the same way.

Aziz and Mackenzie wet their feet by studying the three-player problem from scratch, and their analysis eventually led them to find a bounded envy-free algorithm for the four-player case, which they posted online last year.

They couldn’t immediately see how to extend their algorithm to more than four players, but they dived feverishly into the problem. “After we submitted our paper for the four-agent case, we were really keen that we should try it before someone much more experienced, much more clever would generalize it to the n-agent case,” Aziz said. After about a year, their efforts succeeded.

As with the Selfridge-Conway algorithm, Aziz and Mackenzie’s complicated protocol repeatedly asks individual players to cut cake into n equal pieces, then asks other players to make trims and choose pieces of cake. But the algorithm also carries out other steps, such as periodically exchanging portions of players’ cake stashes in a carefully controlled way, with an eye toward increasing the number of domination relationships between players.

These domination relationships allow Aziz and Mackenzie to reduce the complexity of the problem: If, for example, three players dominate all the others, those three can be sent away with their slices of cake—they’ll be happy no matter who gets the remaining trimmings. Now there are fewer players to worry about, and after a bounded number of such steps, everyone has been satisfied and all the cake given out.

“Seeing, in retrospect, how complicated the algorithm is, it’s not surprising that it took a long time before somebody found one,” Procaccia said. But Aziz and Mackenzie already think that they can simplify their algorithm considerably, to one that doesn’t need the cake exchanges and takes fewer than n^n^n steps. They are currently writing up these new results, Aziz said.

Even a simpler such algorithm would be unlikely to have practical implications, Brams cautioned, since the cake portions that players receive would typically include many tiny crumbs from different parts of the cake—not a feasible approach if you’re dividing something like a tract of land.

But for mathematicians and computer scientists who study cake cutting, the new result “resets the subject,” Stromquist said.

Now that researchers know it’s possible to fairly divide cake in a bounded number of steps, the next goal, Procaccia said, is to understand the huge gulf between Aziz and Mackenzie’s upper bound and the existing lower bound on the number of cuts needed to divide a cake.

Procaccia had previously proved that an envy-free cake-cutting algorithm will require at least about n² steps—but that bound is minuscule compared to n^n^n^n^n^n or even n^n^n.

Researchers now have to figure out how to close this gap, Aziz said. “I think there can be progress in both directions.”

For more insights like this, visit our website at www.international-maths-challenge.com.

Credit of the article given to Erica Klarreich & Quanta Magazine

The distribution of prime numbers from 1 to 76,800, from left to right and top to bottom. A black pixel means that the number is first, while a white pixel means that it is not.

On December 26, 2017, J. Pace, G. Woltman, S. Kurowski, A. Blosser, and their co-authors announced the discovery of a new prime number): 2⁷⁷²³²⁹¹⁷-1. It’s an excellent opportunity to take a small tour through the wonderful world of prime numbers to see how this result was achieved and why it is so interesting.

A prime number is one that is divisible only by itself and the number 1, that is, essentially a number that has no divisor. Some speak of prime numbers as the atoms of the mathematical universe, others as precious stones.

US stamp featuring the prime number 2¹¹²¹³-1. Author provided, CC BY

It is to Euclid that we owe the first two definitions of a prime number:

• Any number is the unique product of prime factors.
• They are infinite in number. The demonstration of this result is regarded as the first proof by absurdity: Suppose there is only a finite number of prime numbers, so they are all smaller than an integer n. Any integer greater than n would therefore be divisible by a prime number less than n. However, the number (2 * 3 * … * n) + 1 is not divisible by any integer from 2 to n since the remainder of the division is always 1 – a contradiction of the preceding sentence.

Eratosthenes, who lived from -276 to -194, proposed a process that allows us to find all prime numbers less than a given natural number N. The process consists of eliminating from a table integers from 2 to N that are multiples of those numbers. By deleting all the multiples, there remain only integers that are not multiples of any integer, and so are prime numbers. The search for efficient algorithms is an active research topic – for example for the Lucas-Lehmer test.

After the Greek era, there was a long dark period that lasted until the end of the 16th century and the arrival of French theologian and mathematician Marin Mersenne (1588-1648). He was an advocate of Catholic orthodoxy, yet also believed that religion must welcome any updated truth. He was a Cartesian and translator of Galileo.

Mersenne was looking for a formula that would generate all the prime numbers. In particular, he studied the numbers M_p = 2^p-1, where p is prime. These numbers are now called Mersenne numbers or Mersenne primes. In 1644 he wrote that Mp is prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257, and compound – in other words, non-prime – for the other 44 lower p values at 257. These definition actually commits five errors: M61, M89 and M107 are prime, while M67 and M257 are not.

The new prime number discovered at the very end of 2017 corresponds to M77232917. It has 23,249,425 digits – almost a million digits more than the previous record-holding prime. If the number were contained by a document written in the font Times New Roman with a point size of 10 and standard page margins, it would fill 3,845 pages.

The official date of discovery of a prime number is the day that someone declares the result. This is in keeping with tradition: M4253 is reputed not to have one because in 1961 the American mathematician Alexander Hurwitz read a printer output from the end forward, and found M4423 a few seconds before seeing M4253. The previous Mersenne number also had a complicated history: the computer reported the result to the server on September 17, 2015, but a bug blocked the email. The prime number remained unnoticed until January 7, 2016.

Quantum cryptography

We often refer to the use of prime numbers in cryptography, but they’re too big to be really useful. (There is hope that quantum cryptography will change things.) Historically, Mersenne’s search for prime numbers has been used as a test for computer hardware. In 2016, the premium95 community discovered a flaw in Intel’s Skylake CPU as well as many PCs. This prime number was found as part of the Great Internet Mersenne Prime Search Project (GIMPS).

2⁷⁷²³²⁹¹⁷-1 is the 50th Mersenne prime and if the challenge to discover the 51st tempts you, the verification program is available to all – and there’s even a $3,000 prize.

For more insights like this, visit our website at www.international-maths-challenge.com.
Credit of the article given to Avner Bar-Hen

Credit: Gaetan Charbonneau Getty Images

The science and art of password setting and cracking continues to evolve, as does the war between password users and abusers

At one time or another, we have all been frustrated by trying to set a password, only to have it rejected as too weak. We are also told to change our choices regularly. Obviously such measures add safety, but how exactly?

I will explain the mathematical rationale for some standard advice, including clarifying why six characters are not enough for a good password and why you should never use only lowercase letters. I will also explain how hackers can uncover passwords even when stolen data sets lack them.

Choose#W!sely@*

Here is the logic behind setting hack-resistant passwords. When you are asked to create a password of a certain length and combination of elements, your choice will fit into the realm of all unique options that conform to that rule—into the “space” of possibilities. For example, if you were told to use six lowercase letters—such as, afzjxd, auntie, secret, wwwwww—the space would contain 26⁶, or 308,915,776, possibilities. In other words, there are 26 possible choices for the first letter, 26 possible choices for the second, and so forth. These choices are independent: you do not have to use different letters, so the size of the password space is the product of the possibilities, or 26 x 26 x 26 x 26 x 26 x 26 = 26⁶.

If you are told to select a 12-character password that can include uppercase and lowercase letters, the 10 digits and 10 symbols (say, !, @, #, $, %, ^, &, ?, / and +), you would have 72 possibilities for each of the 12 characters of the password. The size of the possibility space would then be 72¹² (19,408,409,961,765,342,806,016, or close to 19 x 10²¹).

That is more than 62 trillion times the size of the first space. A computer running through all the possibilities for your 12-character password one by one would take 62 trillion times longer. If your computer spent a second visiting the six-character space, it would have to devote two million years to examining each of the passwords in the 12-character space. The multitude of possibilities makes it impractical for a hacker to carry out a plan of attack that might have been feasible for the six-character space.

Calculating the size of these spaces by computer usually involves counting the number of binary digits in the number of possibilities. That number, N, is derived from this formula: 1 + integer(log₂(N)). In the formula, the value of log₂(N) is a real number with many decimal places, such as log₂(26⁶) = 28.202638…. The “integer” in the formula indicates that the decimal portion of that log value is omitted, rounding down to a whole number—as in integer(28.202638… 28). For the example of six lowercase letters above, the computation results in 29 bits; for the more complex, 12-character example, it is 75 bits. (Mathematicians refer to the possibility spaces as having entropy of 29 and 75 bits, respectively.) The French National Cybersecurity Agency (ANSSI) recommends spaces having a minimum of 100 bits when it comes to passwords or secret keys for encryption systems that absolutely must be secure. Encryption involves representing data in a way that ensures it cannot be retrieved unless a recipient has a secret code-breaking key. In fact, the agency recommends a possibility space of 128 bits to guarantee security for several years. It considers 64 bits to be very small (very weak); 64 to 80 bits to be small; and 80 to 100 bits to be medium (moderately strong).

Moore’s law (which says that the computer-processing power available at a certain price doubles roughly every two years) explains why a relatively weak password will not suffice for long-term use: over time computers using brute force can find passwords faster. Although the pace of Moore’s law appears to be decreasing, it is wise to take it into account for passwords that you hope will remain secure for a long time.

For a truly strong password as defined by ANSSI, you would need, say, a sequence of 16 characters, each taken from a set of 200 characters. This would make a 123-bit space, which would render the password close to impossible to memorize. Therefore, system designers are generally less demanding and accept low- or medium-strength passwords. They insist on long ones only when the passwords are automatically generated by the system, and users do not have to remember them.

There are other ways to guard against password cracking. The simplest is well known and used by credit cards: after three unsuccessful attempts, access is blocked. Alternative ideas have also been suggested, such as doubling the waiting time after each successive failed attempt but allowing the system to reset after a long period, such as 24 hours. These methods, however, are ineffective when an attacker is able to access the system without being detected or if the system cannot be configured to interrupt and disable failed attempts.

How Long Does It Take to Search All Possible Passwords?

For a password to be difficult to crack, it should be chosen randomly from a large set, or “space,” of possibilities. The size, T, of the possibility space is based on the length, A, of the list of valid characters in the password and the number of characters, N, in the password.

The size of this space (T = A^N) may vary considerably.

Each of the following examples specifies values of A, N, T and the number of hours, D, that hackers would have to spend to try every permutation of characters one by one. X is the number of years that will have to pass before the space can be checked in less than one hour, assuming that Moore’s law (the doubling of computing capacity every two years) remains valid. I also assume that in 2019, a computer can explore a billion possibilities per second. I represent this set of assumptions with the following three relationships and consider five possibilities based on values of A and N:

 

Relationships

T = A^N
D = T/(10⁹ × 3,600)
X = 2 log₂[T/(10⁹ × 3,600)]

Results

_________________________________

If A = 26 and N = 6, then T = 308,915,776
D = 0.0000858 computing hour
X = 0; it is already possible to crack all passwords in the space in under an hour

_________________________________

If A = 26 and N = 12, then T = 9.5 × 10¹⁶
D = 26,508 computing hours
X = 29 years before passwords can be cracked in under an hour

_________________________________

If A = 100 and N = 10, then T = 10²⁰
D = 27,777,777 computing hours
X = 49 years before passwords can be cracked in under an hour

_________________________________

If A = 100 and N = 15, then T = 10³⁰
D = 2.7 × 10¹⁷ computing hours
X = 115 years before passwords can be cracked in under an hour

________________________________

If A = 200 and N = 20, then T = 1.05 × 10⁴⁶
D = 2.7 × 10³³ computing hours
X = 222 years before passwords can be cracked in under an hour

Weaponizing Dictionaries and Other Hacker Tricks

Quite often an attacker succeeds in obtaining encrypted passwords or password “fingerprints” (which I will discuss more fully later) from a system. If the hack has not been detected, the interloper may have days or even weeks to attempt to derive the actual passwords.

To understand the subtle processes exploited in such cases, take another look at the possibility space. When I spoke earlier of bit size and password space (or entropy), I implicitly assumed that the user consistently chooses passwords at random. But typically the choice is not random: people tend to select a password they can remember (locomotive) rather than an arbitrary string of characters (xdichqewax).

This practice poses a serious problem for security because it makes passwords vulnerable to so-called dictionary attacks. Lists of commonly used passwords have been collected and classified according to how frequently they are used. Attackers attempt to crack passwords by going through these lists systematically. This method works remarkably well because, in the absence of specific constraints, people naturally choose simple words, surnames, first names and short sentences, which considerably limits the possibilities. In other words, the nonrandom selection of passwords essentially reduces possibility space, which decreases the average number of attempts needed to uncover a password.

If you use password or iloveyou, you are not as clever as you thought! Of course, lists differ according to the country where they are collected and the Web sites involved; they also vary over time.

For four-digit passwords (for example, the PIN code of SIM cards on smartphones), the results are even less imaginative. In 2013, based on a collection of 3.4 million passwords each containing four digits, the DataGenetics Web site reported that the most commonly used four-digit sequence (representing 11 percent of choices) was 1234, followed by 1111 (6 percent) and 0000 (2 percent). The least-used four-digit password was 8068. Careful, though, this ranking may no longer be true now that the result has been published. The 8068 choice appeared only 25 times among the 3.4-million four-digit sequences in the database, which is much less than the 340 uses that would have occurred if each four-digit combination had been used with the same frequency. The first 20 series of four digits are: 1234; 1111; 0000; 1212; 7777; 1004; 2000; 4444; 2222; 6969; 9999; 3333; 5555; 6666; 1122; 1313; 8888; 4321; 2001; 1010.

Even without a password dictionary, using differences in frequency of letter use (or double letters) in a language makes it possible to plan an effective attack. Some attack methods also take into account that, to facilitate memorization, people may choose passwords that have a certain structure—such as A1=B2=C3, AwX2AwX2 or O0o.lli. (which I used for a long time)—or that are derived by combining several simple strings, such as password123 or johnABC0000. Exploiting such regularities makes it possible to for hackers to speed up detection.

Advice for Web Sites

Web sites, too, follow various rules of thumb. The National Institute of Standards and Technology recently published a notice recommending the use of dictionaries to filter users’ password choices.

Among the rules that a good Web server designer absolutely must adhere to is, do not store plaintext lists of usernames and passwords on the computer used to operate the Web site.

The reason is obvious: hackers could access the computer containing this list, either because the site is poorly protected or because the system or processor contains a serious flaw unknown to anyone except the attackers (a so-called zero-day flaw), who can exploit it.

One alternative is to encrypt the passwords on the server: use a secret code that transforms them via an encryption key into what will appear to be random character sequences to anyone who does not possess the decryption key. This method works, but it has two disadvantages. First, it requires decrypting the stored password every time to compare it with the user’s entry, which is inconvenient. Second, and more seriously, the decryption necessary for this comparison requires storing the decryption key in the Web site computer’s memory. This key may therefore be detected by an attacker, which brings us back to the original problem.

A better way to store passwords is through what are called hash functions that produce “fingerprints.” For any data in a file—symbolized as F—a hash function generates a fingerprint. (The process is also called condensing or hashing.) The fingerprint—h(F)—is a fairly short word associated with F but produced in such a way that, in practice, it is impossible to deduce F from h(F). Hash functions are said to be one-way: getting from F to h(F) is easy; getting from h(F) to F is practically impossible. In addition, the hash functions used have the characteristic that even if it is possible for two data inputs, F and F’, to have the same fingerprint (known as a collision), in practice for a given F, it is almost impossible to find an F’ with a fingerprint identical to F.

Using such hash functions allows passwords to be securely stored on a computer. Instead of storing the list of paired usernames and passwords, the server stores only the list of username/fingerprint pairs.

When a user wishes to connect, the server will read the individual’s password, compute the fingerprint and determine whether it corresponds to the list of stored username/fingerprint pairs associated with that username. That maneuver frustrates hackers because even if they have managed to access the list, they will be unable to derive the users’ passwords, inasmuch as it is practically impossible to go from fingerprint to password. Nor can they generate another password with an identical fingerprint to fool the server because it is practically impossible to create collisions.

For more insights like this, visit our website at www.international-maths-challenge.com.

Credit of the article given to Jean-Paul Delahaye

Shutterstock

Why is mathematics so complicated? It’s a question many students will ask while grappling with a particularly complex calculus problem – and their teachers will probably echo while setting or marking tests.

It wasn’t always this way. Many fields of mathematics germinated from the study of real world problems, before the underlying rules and concepts were identified. These rules and concepts were then defined as abstract structures. For instance, algebra, the part of mathematics in which letters and other general symbols are used to represent numbers and quantities in formulas and equations was born from solving problems in arithmetic. Geometry emerged as people worked to solve problems dealing with distances and area in the real world.

That process of moving from the concrete to the abstract scenario is known, appropriately enough, as abstraction. Through abstraction, the underlying essence of a mathematical concept can be extracted. People no longer have to depend on real world objects, as was once the case, to solve a mathematical puzzle. They can now generalise to have wider applications or by matching it to other structures can illuminate similar phenomena. An example is the adding of integers, fractions, complex numbers, vectors and matrices. The concept is the same, but the applications are different.

This evolution was necessary for the development of mathematics, and important for other scientific disciplines too.

Why is this important? Because the growth of abstraction in maths gave disciplines like chemistry, physics, astronomy, geology, meteorology the ability to explain a wide variety of complex physical phenomena that occur in nature. If you grasp the process of abstraction in mathematics, it will equip you to better understand abstraction occurring in other tough science subjects like chemistry or physics.

From the real world to the abstract

The earliest example of abstraction was when humans counted before symbols existed. A sheep herder, for instance, needed to keep track of his flock of sheep without having any sort of symbolic system akin to numbers. So how did he do this to ensure that none of his sheep wandered away or got stolen?

One solution is to obtain a big supply of stones. He then moved the sheep one-by-one into an enclosed area. Each time a sheep passed, he placed a stone in a pile. Once all the sheep had passed, he got rid of the extra stones and was left with a pile of stones representing his flock.

Every time he needed to count the sheep, he removed the stones from his pile; one for each sheep. If he had stones left over, it means some sheep had wandered away or perhaps been stolen. This one-to-one correspondence helped the shepherd to keep track of his flock.

Today, we use the Arabic numbers (also known as the Hindu-Arabic numerals): 0,1,2,3,4,5,6,7,8,9 to represent any integer, that is any whole number.

This is another example of abstraction, and it’s powerful. It means we’re able to handle any amount of sheep, regardless of how many stones we have. We’ve moved from real-world objects – stones, sheep – to the abstract. There is real strength in this: we’ve created a space where the rules are minimalistic, yet the games that can be played are endless.

Another advantage of abstraction is that it reveals a deeper connection between different fields of mathematics. Results in one field can suggest concepts and ideas to be explored in a related field. Occasionally, methods and techniques developed in one field can be directly applied to another field to create similar results.

Tough concepts, better teaching

Of course, abstraction also has its disadvantages. Some of the mathematical subjects taught at university level – Calculus, Real Analysis, Linear Algebra, Topology, Category Theory, Functional Analysis and Set Theory among them – are very advanced examples of abstraction.

These concepts can be quite difficult to learn. They’re often tough to visualise and their rules rather unintuitive to manipulate or reason with. This means students need a degree of mathematical maturity to process the shift from the concrete to the abstract.

Many high school kids, particularly from developing countries, come to university with an undeveloped level of intellectual maturity to handle abstraction. This is because of the way mathematics was taught at high school. I have seen many students struggling, giving up or not even attempting to study mathematics because they weren’t given the right tools at school level and they think that they just “can’t do maths”.

Teachers and lecturers can improve this abstract thinking by being aware of abstractions in their subject and learning to demonstrate abstract concepts through concrete examples. Experiments are also helpful to familiarise and assure students of an abstract concept’s solidity.

This teaching principle is applied in some school systems, such as Montessori, to help children improve their abstract thinking. Not only does this guide them better through the maze of mathematical abstractions but it can be applied to other sciences as well.

For more insights like this, visit our website at www.international-maths-challenge.com.
Credit of the article given to Harry Zandberg Wiggins

Credit: Roy Scott/Getty Images

How to calculate an average if you’re indecisive

So you’ve got some numbers, and you want to produce one number that represents their typical value. If you’ve taken a little bit of math or statistics, you might reach for the mean—the arithmetic mean, to be precise. Add the numbers together and divide by the number of numbers you have. Easy enough.

But perhaps you’re a bit of a Chidi, and furthermore you made the mistake of learning about the geometric mean at some point. The geometric mean is another measure of central tendency, as statisticians say. The geometric mean is like the arithmetic mean, but you change addition to multiplication and division to taking roots. To find the geometric mean of two numbers, multiply them together and take the square root of their product. (This operation can only be performed on two numbers that are either both positive or both negative. But the world is negative enough. Let’s just think about positive numbers!) True to its name, this mean has a nice geometric interpretation: it is the side length of a square with the same area as a rectangle having your two numbers as side lengths. To find the geometric mean of a lot of numbers—let’s say n of them—multiply them all together and take the nth root.

Knowing about both the arithmetic and geometric means, you are wracked with internal turmoil: Which mean will best represent your numbers?

The arithmetic mean is nice. It seems very balanced and equitable. But the geometric mean has its merits as well. It is a useful tool when you’re working with processes that work multiplicatively instead of additively, like interest rates. It pulls larger numbers closer to smaller numbers more than the arithmetic mean does, whether you are taking the geometric mean of just two numbers or many numbers. The geometric mean might be a better representative than the arithmetic mean or even the median for a data set that has a lot of smaller values and a few large ones—say, income distributions.

Which will it be? Decisions are so hard!

Why not both?

The arithmetic-geometric mean lets you find a number between your two favorite positive numbers that is a compromise between the arithmetic and geometric means, letting your inner Chidi rest easy.

Finding the arithmetic-geometric mean is an iterative process. Each step produces two numbers: the arithmetic and geometric means of the previous two numbers. So starting with, say, 1 and 2, the first step produces the two numbers 3/2 and √2. At the next step, you find the arithmetic mean of 3/2 and √2, which is approximately 1.457, and the geometric mean of 3/2 and √2, which is approximately 1.456. At that point, the two values you’re getting are already very close together, and subsequent iterations will produce two numbers that are arbitrarily close together. The limit of both the arithmetic and geometric means produced in this process is the same, so it is called the arithmetic-geometric mean. The arithmetic-geometric mean of 1 and 2 is 1.45679…; a bit disappointing in that it would be more fun if it started 1.456789, but a satisfying answer nonetheless.

The approximations of the arithmetic-geometric mean of two numbers get very close together very quickly, so the process has been used to find good approximations for irrational numbers, as in this paper about how to use it to approximate π.

What if you have more than two numbers? As far as I can tell, no one has ever defined the arithmetic-geometric mean for an arbitrary set of positive numbers, but that didn’t stop me. I’m not going to use the name arithmetic-geometric mean for the generalization to make sure nobody thinks it’s an “official” math term. Instead, I’ll call it the ditherer’s mean.

For the arithmetic-geometric mean of two numbers, we had an iterative process that gave us two numbers at every step. One way of thinking about it is that we replaced the smallest number with the geometric mean of the previous numbers and the largest number with the arithmetic mean of them. We’ll do the same thing for the ditherer’s mean.

To take the ditherer’s mean of n numbers, we want an iterative process that gives us n numbers at each step. So at each step, we replace the smallest number from the previous list of numbers with the geometric mean of the previous numbers and the largest number with the arithmetic mean of the numbers.

Let’s take a look at a set of 4 numbers to get a feel for how the process works. We’ll start with the numbers 1, 5, 20, and 26. The arithmetic mean of these numbers is 13, and the geometric mean is approximately 7.14. So we replace the largest and smallest numbers in our first list with 13 and 7.14. Now we have the numbers 5, 7.14, 13, and 20. We repeat the process. The arithmetic mean of those four numbers is about 11.285. The geometric mean is about 9.82. Now our list is 7.14, 9.82, 11.285, and 13. The arithmetic mean is 10.31 and the geometric mean is 10.07. Keep going: 9.82, 10.07, 10.31, 11.285. Then 10.07, 10.31, 10.35, 10.37. Progress! A few more iterations, and it’s clear the numbers are getting closer and closer together, landing around 10.3.

The arithmetic-geometric mean of two numbers has been a useful concept for mathematics. The iterative process that produces it converges very quickly, so it has been used to compute approximations quickly and accurately, as in this paper about computing π using the arithmetic-geometric mean. As far as I can tell, mathematicians have not yet found use for the ditherer’s mean, but I hope it will help some indecisive people take an average and move on with their lives.

There you have it: Now you can find an average of a set of positive numbers without having to choose between their arithmetic and geometric means. Isn’t it wonderful the way math always gives you a tidy answer with no room for uncertainty or ambiguity?

Wait, what’s that? Harmonic mean? Heronian mean? Identric mean? Nooooooooo!

For more insights like this, visit our website at www.international-maths-challenge.com.

Credit of the article given to Evelyn Lamb

Some 20 years ago, my colleague Dr. Chau Tran and I developed a way to simulate the trajectories of millions of basketballs on the computer.

We went to the coaches and assistant coaches at North Carolina State University, where we are based, and told them we had this uncommon ability to study basketball shots very carefully.

Their first question was simple: “What’s the best free throw?” Should the shooter aim towards the front of the hoop or the back? Does it depend on whether the shooter is short or tall?

Math offers a unique perspective. It speeds up the amount of time it takes to see the patterns behind the best shots. For the most part, we discovered things that the players and coaches already knew – but every so often, we came across a new insight.

Simulating millions of shots

From a mathematical viewpoint, basketball is a game of trajectories. These trajectories are unique in that the ball’s motion doesn’t change much when it’s flying through the air, but then rapidly changes over milliseconds when the ball collides with the the hoop or the backboard.

To simulate millions of trajectories without the code taking too long to run, we tried any trick we could think of. We figured out how to go from modestly changing motion to rapidly changing motion, such as when the ball bounces on the rim or off the backboard. We learned how to turn large numbers of trajectories into statistical probabilities. We even created fictitious trajectories in which the ball magically passes through all of the physical obstacles (hoop, backboard, back plate) except for one, to see where it collides first.

How a mathematician sees a free throw. Larry Silverberg, CC BY-SA

 

The free throw was the first shot that my colleague and I studied in detail. In close games, teams can win and lose at the free-throw line. What’s more, the free throw is uncontested, so perfection in the free throw can pay off big. Top teams tend to shoot the free shot well.

Our program could tell us what chances the shooter had in sinking a free throw – and help us figure out what he was doing right or wrong.

Breaking down the free throw

We studied the free throw for about five years.

One of the first things we learned from our simulations and by watching TV footage was that players with the same consistency can shoot free throws with anywhere from 75 to 90 percent accuracy. The difference was that the 90 percent players were being consistent at the right shot – the best trajectory.

The fate of a free throw is set the instant the ball leaves the player’s fingertips, so we looked closely at the “launch conditions” of the shot. The ball is located at some height above the floor. It has a rate at which it is spinning backwards (called backspin), and it has a launch speed and a launch angle. Since the shooter never launches the ball the same way, small differences account for a shooter’s consistency.

We found that about 3 hertz of backspin is the best amount; more than that does not help. It takes about 1 second for a ball to reach the basket, so 3 hertz equates to three revolutions in the air, from the instant the ball leaves the player’s hands to when it reaches the basket.

Next, assuming the player releases the ball at 7 feet above the ground, a launch angle of about 52 degrees is best. In that angle, the launch speed is the lowest, and the probability of the shot being successful is the greatest. At 52 degrees, the shooter can be off a degree or more either way without a large effect on the shot’s success.

However, launch speed is quite the opposite. It’s the hardest variable for a player to control. Release the ball too slowly and the shot is short; release it too fast and the shot is long. A player needs to memorize the motion of her entire body during release to impart the same speed consistently.

All else being the same, players who release from higher above the floor have a higher shooting percentage. That’s interesting, because our coaches at N.C. State and others I have talked say that taller players tend to shoot the free throw worse than shorter players do. It seems that the shorter players must try harder.

The last release condition was the most surprising: the aim point of the free throw. We found that the player should aim the ball to the back of the rim. Basically, the back of the rim is more forgiving than the front of the rim. At a release height of 7 feet, the gap between the ball and the back of the ring should be less than 2 inches. A small gap is best whether launching at low or high release heights.

Lessons learned

So what does this all mean for players out there aspiring to improve their free throw?

Our research suggests that players should aim the ball beyond the center of the rim. Launch the ball at a high angle and as high above the ground as possible. (The ball, at the highest point of its arc, should reach the top of the backboard.) Line up the ball to eliminate the side angle. And try to launch the ball with smooth body motion, to produce a consistent launch speed.

In the past few years, we’ve expanded our work to study where the best bank shots strike the backboard and developed a tool for anyone who wants to perfect it.

With tournament play underway, I’m reminded of how competitive the game has become, and how it has truly become a game of inches. As an old basketball player, like many of you, I enjoy watching the game – and, every so often, catching a glimpse of that perfect free throw.

For more insights like this, visit our website at www.international-maths-challenge.com.
Credit of the article given to Larry M. Silverberg