Advertisement

We need your help now

Support from readers like you keeps The Journal open.

You are visiting us because we have something you value. Independent, unbiased news that tells the truth. Advertising revenue goes some way to support our mission, but this year it has not been enough.

If you've seen value in our reporting, please contribute what you can, so we can continue to produce accurate and meaningful journalism. For everyone who needs it.

Abacus not required. abacus via Shutterstock

How to guess any number under 1,000 in ten steps or less

Here’s a fun party trick to hone in the weeks to come.

HERE IS A fun math party trick.

Tell someone to pick a number between 1 and 1,000. Your goal is to guess the number.

For each guess you make, your friend tells you one of three things: you guessed the number, your guess was high, or your guess was low.

Amazingly, if you guess properly, it is possible to get to any number your friend chooses in 10 or fewer guesses.

The trick to this is to constantly be cutting the amount of numbers you have to consider in half. This process demonstrates binary search, a foundational concept in technology. But more on that later.

How to guess the number in 10 steps or under

Suppose your friend chooses the number 334.

Your First Guess: In this game, your first guess should always be 500, halfway between 1 and 1000. So, you guess 500, and your friend tells you that their number is lower. Now you know that the number is somewhere between 1 and 500, and you have knocked out everything between 500 and 1000. You have, in one guess, already gotten rid of half the possibilities.

Your Second Guess:You know that the number is between 1 and 500, so you again take the halfway point between these two, and you guess 250. Now your friend tells you your guess is too low, so you know the number is somewhere between 250 and 500. In just two steps, you have knocked out 750 numbers, and are just looking at about 250 numbers, a quarter of our original set.

Keep Doing This: Your next guess is halfway between 250 and 500, or 375. Your friend tells you this is too high, so now you know that the number is between 250 and 375. You have reduced your range to about 125 possibilities.

The fourth guess is the midpoint of 250 and 375: Unfortunately, this is a decimal number – 312.5, but we can simply round up to 313. This guess is too low, but we have again eliminated half the remaining numbers, leaving us with the 61 numbers between 313 and 375.

Your fifth guess is halfway between 313 and 375: 344. Again, this is too high, but you’re down to the 30 numbers between 313 and 344.

Your sixth guess is halfway between 313 and 344: 328.5, rounded up to 329. Too low. You know the number is between 329 and 344, leaving just 14 possibilities.

Your seventh guess is halfway between 329 and 344: 336.5, rounded up to 337. Too high, but you’re getting close — only the seven numbers between 329 and 227 are left.

Your eighth guess is halfway between 329 and 337: 333. Juuust too low. But now there are just three remaining possibilities — you know the number is between 333 and 337, so it must be one of 334, 335, or 336.

Your ninth guess is the middle option of 335, and you are told that your guess is too high.

And now you know that the number is between 333 and 335. There is only one such number, and so your tenth, and final guess, is 334, your friend’s number.

This process will work for any number between 1 and 1000, and you will always find the number within 10 guesses.

Binary search

This game is a simple example of a binary search process.

This works well for any ordered list, like a directory of employees at a corporation, ordered by name. Suppose we are trying to find a particular name on the list.

We start by comparing the desired name to the middle name in the list. If they match, then yay! We are done.

If the middle name comes after the desired name, we throw out the second half of the list, and just look at the first half.

If the middle name comes before the desired name, we do the opposite — dump the names before the middle name, and just search the second half of the original list. Then we just keep repeating this process, throwing out half the remaining names each time, until we find our name.

This is such a simple, recursive process that it is ideally suited to being run on computers, and this is indeed how most database systems search through sorted lists of data.

One of the coolest things about binary search is that the number of steps you need to find your target increases logarithmically with the size of the set you are looking in. What this means is that if you double the size of your set, you only wind up adding one extra step. If I wanted to find a number between 1 and 2000, my first guess is going to be 1000 (halfway between 1 and 2000), and then I’ll be looking at either the numbers between 1 and 1000 or between 1001 and 2000, and we are back where we started — trying to find one number among a thousand numbers.

Extending this out, if we wanted to find a number between 1 and 1,000,000, we actually only need 20 steps to get to the number. For those of you familiar with logarithms, this is because the base 2 logarithm of 1,000,000 is just under 20.

Processes like this that add steps at a logarithmic rate with respect to the size of the input are pretty rare — usually, if I double the size of my input, I at least double the number of steps I need to take to solve my problem, and often need to add many, many more steps than that.

Binary search is a great example of using a very simple concept — repeatedly cutting my search region in half by always guessing the middle number — and getting a very powerful tool from that concept. This is one of the central, big ideas in math: Start with a simple notion, and discover all the interesting, often surprising, implications of that notion.

- Andy Kiersz

Maths Week puzzles>
Kids who do well on this test may have unrealised potential>

Readers like you are keeping these stories free for everyone...
A mix of advertising and supporting contributions helps keep paywalls away from valuable information like this article. Over 5,000 readers like you have already stepped up and support us with a monthly payment or a once-off donation.

Published with permission from
View 28 comments
Close
28 Comments
    Install the app to use these features.
    Mute Harry
    Favourite Harry
    Report
    May 16th 2016, 9:05 AM

    He sounds like great craic

    196
    Install the app to use these features.
    Mute ray.farrelly
    Favourite ray.farrelly
    Report
    May 16th 2016, 9:11 AM

    He must be a blueshirt.

    61
    Install the app to use these features.
    Mute David Conroy
    Favourite David Conroy
    Report
    May 16th 2016, 10:08 AM

    I wonder could we get him over here ? Savings of about €150k on salary and he will clean up crime as well !

    90
    See 5 more replies ▾
    Install the app to use these features.
    Mute GameOverMan
    Favourite GameOverMan
    Report
    May 16th 2016, 10:18 AM

    This geriatric tosser wont stand up to any real criminals. Hes just another dictator who’ll be hard on citizens while he lives off backhanders from organised crime. Where are all the assassins gone?

    64
    Install the app to use these features.
    Mute Keelan O'neill
    Favourite Keelan O'neill
    Report
    May 16th 2016, 11:00 AM

    They’re off making a film with Michael Fassbender.

    31
    Install the app to use these features.
    Mute ktsiwot
    Favourite ktsiwot
    Report
    May 16th 2016, 11:05 AM

    Makes Donald sound like a pinky left liberal.

    46
    Install the app to use these features.
    Mute Anton Friendo
    Favourite Anton Friendo
    Report
    May 16th 2016, 12:28 PM

    Hillary can supply him with the arms and ammo from her ISIS stash

    32
    Install the app to use these features.
    Mute James Costello
    Favourite James Costello
    Report
    May 17th 2016, 9:53 AM

    Could do with him in Ireland !!

    2
    Install the app to use these features.
    Mute postman pat
    Favourite postman pat
    Report
    May 16th 2016, 9:32 AM

    Snipers should be brought in here to sort out the gangland problem

    71
    Install the app to use these features.
    Mute John Judd
    Favourite John Judd
    Report
    May 16th 2016, 9:25 AM

    Sounds more like a dictator!

    59
    Install the app to use these features.
    Mute Davy Boy
    Favourite Davy Boy
    Report
    May 16th 2016, 9:21 AM

    Interesting approach good luck with that

    58
    Install the app to use these features.
    Mute Mark Andrew Salmon
    Favourite Mark Andrew Salmon
    Report
    May 16th 2016, 9:52 AM

    Just rhink about this for a minute. If parents let their kids out at night he will jail the parents. So who will look after the kids then? The State? Who will pay for that? It just demonstrates the kind of knee jerk red neck thinking of this moron. He doesn’t fight crime he just gets the State to commit crime instead of the “private sector”. Murders become state sanctioned executions and robberies become “contributions”. He is definitely a dictator in the making and the people of the Phillipines will dearly regret electing him.

    57
    Install the app to use these features.
    Mute Mark Ryan
    Favourite Mark Ryan
    Report
    May 16th 2016, 3:20 PM

    Or maybe it will stop parents allowing their children out at night..

    18
    Install the app to use these features.
    Mute Khyn Yap
    Favourite Khyn Yap
    Report
    May 17th 2016, 6:07 AM

    he has been doing this for 20 years in davao. we have a Penal code. laws of the land that protects minors from abuse and neglect. before we assume lets read the facts first.

    4
    Install the app to use these features.
    Mute Mick Jordan
    Favourite Mick Jordan
    Report
    May 16th 2016, 11:37 AM

    People on here seem to forget he was freely elected with a massive majority of the vote. I know many are opposed to the Death Penalty. But look at what crimes he is proposing to introduce it for. Murder, Terrorism, Rape, Child Molestation, Armed Robbery and Drug Smuggling/Dealing. All crimes many on here have said should be dealt with in the most draconian manner. And how many times have we read stories of feral kids here roaming in packs, attacking frontline emergency personnel and have read comments about making the parents pay. As for his shoot to kill policy. Simple solution, don’t resist being arrested.

    49
    Install the app to use these features.
    Mute Deborah Behan
    Favourite Deborah Behan
    Report
    May 16th 2016, 12:33 PM

    And it’s that simple is it?

    24
    Install the app to use these features.
    Mute Mick Jordan
    Favourite Mick Jordan
    Report
    May 16th 2016, 12:51 PM

    Yes Deborah, it is that simple.

    25
    See 7 more replies ▾
    Install the app to use these features.
    Mute Malachi
    Favourite Malachi
    Report
    May 16th 2016, 1:11 PM

    Do you really think drug dealers/smugglers should be hung?

    23
    Install the app to use these features.
    Mute Ross Stewart
    Favourite Ross Stewart
    Report
    May 16th 2016, 1:41 PM

    Yes Mick, you are that simple

    16
    Install the app to use these features.
    Mute Mick Jordan
    Favourite Mick Jordan
    Report
    May 16th 2016, 3:05 PM

    I never pretended to be complicated Ross. Only the pretentious try to be.

    14
    Install the app to use these features.
    Mute theresa marie
    Favourite theresa marie
    Report
    May 16th 2016, 3:40 PM

    Hi Mick, I am from the Philippines it is very sad to think my people forgot that they got rid of Martial Law and what the call a dictator only to go back to this. I wish and pray it works for their benefit and future.

    12
    Install the app to use these features.
    Mute Mick Jordan
    Favourite Mick Jordan
    Report
    May 16th 2016, 3:58 PM

    As I said Theresa the vast majority of your countrymen voted for him in free elections knowing full well what his policies were and his history as mayor. People must have seen no alternative in the other candidates when it came to tackling crime.

    12
    Install the app to use these features.
    Mute Ross Stewart
    Favourite Ross Stewart
    Report
    May 16th 2016, 5:02 PM

    Hitler, Mugabe, Al bashir, lukashenko and most importantly for this story, Ferdinand Marcos were all elected and look how their ruling turned out.

    7
    Install the app to use these features.
    Mute Mick Jordan
    Favourite Mick Jordan
    Report
    May 16th 2016, 5:40 PM

    Ross. We got Enda. Nobody is claiming that a Free Democratic election is perfect but it is the Peoples choice. And in this case he was elected by a vast majority of the Filipino people. He made no attempt to hide his policies, his history as Mayor of Davao city was there for all to see and yet still they voted for him in their millions.

    9
    Install the app to use these features.
    Mute Nick Allen
    Favourite Nick Allen
    Report
    May 16th 2016, 9:18 AM

    And we think we are hard done by with Enda in charge

    38
    Install the app to use these features.
    Mute Ross Stewart
    Favourite Ross Stewart
    Report
    May 16th 2016, 9:48 AM

    Just a different type of dictator

    40
    Install the app to use these features.
    Mute Jimmy Murphy
    Favourite Jimmy Murphy
    Report
    May 16th 2016, 9:15 AM

    What a nice fellow.

    37
    Install the app to use these features.
    Mute Stiofán Na Mara
    Favourite Stiofán Na Mara
    Report
    May 16th 2016, 9:24 AM

    They should fear the IMF mafia more and the march of aggressive neo liberal capitalism which has been destroying them. Watch this documentary.. https://www.youtube.com/watch?v=79bZ71fUZRU

    32
    Install the app to use these features.
    Mute Jason O Neill
    Favourite Jason O Neill
    Report
    May 16th 2016, 10:16 AM

    oh a good crack down on drug dealers, rapist and murders sounds like a great idea. and for parents who let their kids walk the streets at night in such a dangerous place should not be allow look after kids.

    28
    Install the app to use these features.
    Mute Robbi Cairdiúil
    Favourite Robbi Cairdiúil
    Report
    May 16th 2016, 12:20 PM

    Extra-judicial killings are not the way forward no matter what. And I have always been perfectly safe in the Philippines.

    19
    Install the app to use these features.
    Mute Mark Ryan
    Favourite Mark Ryan
    Report
    May 16th 2016, 3:20 PM

    It’s an interesting case study all the same.

    5
    Install the app to use these features.
    Mute Brian Lynch
    Favourite Brian Lynch
    Report
    May 16th 2016, 7:33 PM

    I was in Davao last year and the people there love him. It was extremely safe by day and night although there is a very visible police force on the streets all fully armed. Smoking is banned literally everywhere and bars close at 1:30am. People in the city all seemed very happy and say it’s a god send from the days when Davao was the murder Capitol of the Phillipines. Whether such draconian ideology work across the nation remains to be seen but with so many phillipinos sick of crime and corruption you can see why they voted for him….

    19
    Install the app to use these features.
    Mute Robbi Cairdiúil
    Favourite Robbi Cairdiúil
    Report
    May 16th 2016, 12:19 PM

    The majority of my friends here in Belfast are Filipino and I’m surprised by the support for him given the votes they cast in our recent election in the north. Why Miriam Defensor Santiago’s polling was so low is staggering – a highly intelligent, able, socially liberal academic and former International Criminal Court Judge. She may be mouthy but she was more than able. For Duterte to win, and for Marcos to poll astronomically higher than Miriam is completely and totally beyond me. It’s American-style cult of personality madness!

    12
    Install the app to use these features.
    Mute Mark Ryan
    Favourite Mark Ryan
    Report
    May 16th 2016, 3:22 PM

    Or maybe the country want a serious change

    12
    Install the app to use these features.
    Mute theresa marie
    Favourite theresa marie
    Report
    May 16th 2016, 4:08 PM

    Robbi, Mirriam was the only deserving candidate, if not for her being very sick ( granted she said her stage 4 cancer is in remission) people are in no doubt would have voted for her. Marcos is running for VP and Merriam is for President so their votes don’t connect.

    4
    Install the app to use these features.
    Mute China Photo Daily
    Favourite China Photo Daily
    Report
    May 16th 2016, 6:12 PM

    This article perfectly encapsulates how bad the AFP is. Duterte is a plague and is a step backwards for The Philippines, it’s literally the easiest honest hit piece in the world to write but they just can’t help themselves. “He claimed Davao is one of the safest cities in the Philippines” well is it or isn’t it? How hard is it to quote the figures to us? Are they that afraid of admitting he may have been successful at one thing? God just report the facts and leave out the spin.

    7
    Install the app to use these features.
    Mute prouesse f
    Favourite prouesse f
    Report
    May 16th 2016, 11:23 AM

    He must be Muslim…

    5
    Install the app to use these features.
    Mute June Rose-Sommer
    Favourite June Rose-Sommer
    Report
    May 17th 2016, 1:01 PM

    He sounds absolutely crazy!!! I fear for the country!!!

    1
Submit a report
Please help us understand how this comment violates our community guidelines.
Thank you for the feedback
Your feedback has been sent to our team for review.
JournalTv
News in 60 seconds