Excellent Math Riddle

Page 3 of 8 [ 114 posts ] Go to page Previous 1, 2, 3, 4, 5, 6 ... 8 Next

Previous topic | Next topic

aequitas1
Tufted Titmouse

Joined: 8 May 2013
Age: 38
Gender: Male
Posts: 41

11 May 2013, 12:25 pm

eric76 wrote:

Ellingtonia wrote:

I think I have a way for 999 to win with certainty, with a possibility for 1000 to win. The only problem is that it requires the first wizard to intentionally guess the wrong answer, sacrificing his chance of becoming an archmage.

So the first wizard sees 999 numbers in front of him, leaving 2 numbers to choose from. Instead of guessing either of these numbers, he adds them together and guesses that number e.g. if he knows his number is either 312 or 115 he will guess 427

The next wizard sees 998 numbers in front, and so knows that his number must be one of three numbers. He then finds which two of these three numbers add together to get the first wizard's guess, and then guesses the third number. e.g. if he knows his number must be 312, 115 or 512, then he can work out that the two numbers that the first wizard couldn't see must have been 312 and 115, as they add up to 427. He then knows that his number must be 512.

Similarly, the third wizard can immediately narrow his number down to four possibilities. He also knows that as long as everyone follows the plan, the second wizard must have guessed correctly, so he can eliminate that number, leaving three possibilities. He then applies the same technique the second wizard did to eliminate two more, leaving his number. e.g. If he sees that his possibilities are 312, 115, 512 and 65, he can immediately eliminate 512 as that was the second wizard's number. He then uses the same thinking that the second wizard did to eliminate 312 and 115, and so guesses 65 correctly.

Each wizard in succesion uses this same method of first eliminating all numbers in front of him, then all guesses made before him (except for the first guess) to leave him with three possibilities. He then finds which two of these three numbers add together to get the first wizard's guess, and then guesses the remaining number.

The only 'hiccup' comes for the wizard who has the number that the first wizard guessed. He would use the technique to narrow his possibilities down to three, so in our example he would be left with 312, 155 and 427. He knows that his number is 427, but he cannot guess this as it has already been guessed. Instead he guesses an obviously wrong number, any number over 1001. This tells all the wizards who come after him that his number was the same as that first guess, allowing them to succeed even if he cannot.

So this is how 999 can win with certainty. It is also possible to one more to win, if the first wizard sees that his two possibilities add together to make a number greater than 1001, he can guess this number and then every wizard after him can guess right. There is no 'hiccup' as no wizard will have a hat with that number on it.

I have to think about this approach a bit more, but there is an obvious discrepancy. If the first wizard to guess guesses the wrong one than he not only doesn't become archmage, but neither does the wizard who's hat he guessed if that number is a valid wizard hat number. So you can only guarantee that 998 can win.

However, if you set the guess as 10,000 plus the sum of the two hats he doesn't see, then the wizard with the hat can still get his hat correct.

His argumentation is invalid as per the limitations stated and will not solve for 998.

You both have stated things that may or may not be correct while also stating things in contradiction with the limitations stated. I solved for 998 wizards but I used an entirely different strategy.

Either way, you're all advancing very quickly to a more dynamical approach to the problem. Keep up the good work!

Ellingtonia
Sea Gull

Joined: 9 Oct 2011
Age: 33
Gender: Male
Posts: 200

11 May 2013, 12:28 pm

Somberlain wrote:

a) For 500: Odd wizards can give clue to even wizards by guessing closer numbers to their actual number.

Also subtracting numbers can eliminate ''over 1001'' problem for b).

I think that subtracting numbers does solve the "over 1001" problem, but raises another.

Say the missing number is 115, the first number is 312 and the second is 509. The first wizard would find the difference of his two possibilities (115, 312) and guess 197. The second wizard would look his three possibilities and not know whether to eliminate 115 and 312 (if wizard #1 had done 312-115=197) or to eliminate 312 and 509 (if wizard #1 had done 509-312=197). The second wizard would have to guess between 509 and 115.

eric76
Veteran
Veteran

Joined: 31 Aug 2012
Gender: Male
Posts: 10,660
Location: In the heart of the dust bowl

11 May 2013, 12:30 pm

aequitas1 wrote:

eric76 wrote:

Ellingtonia wrote:

Unfortunately, I have to fix something to eat and then go change a radio out on top of a grain elevator in a few minutes so I probably won't be around to participate for at least a couple of hours.

aequitas1
Tufted Titmouse

Joined: 8 May 2013
Age: 38
Gender: Male
Posts: 41

11 May 2013, 12:41 pm

Somberlain wrote:

a) For 500: Odd wizards can give clue to even wizards by guessing closer numbers to their actual number.

Also subtracting numbers can eliminate ''over 1001'' problem for b).

I generalized the problem and came up with an entirely different strategy. What if the hat value of the second wizard falls equidistant between the two missing values?

This makes certainty under this strategy impossible.

aequitas1
Tufted Titmouse

Joined: 8 May 2013
Age: 38
Gender: Male
Posts: 41

11 May 2013, 12:45 pm

eric76 wrote:

Unfortunately, I have to fix something to eat and then go change a radio out on top of a grain elevator in a few minutes so I probably won't be around to participate for at least a couple of hours.

I promise not to reveal my solution. I may just state that anyone wishing to see the solution for 998 to message me because I want to see how far people roll with this problem.

naturalplastic
Veteran
Veteran

Joined: 26 Aug 2010
Age: 69
Gender: Male
Posts: 35,189
Location: temperate zone

11 May 2013, 1:24 pm

Somberlain wrote:

a)
Also subtracting numbers can eliminate ''over 1001'' problem for b).

Is there a dope-slap emoticon?

That would just replace the 'over 1001 problem' with the 'no negative numbers problem"!

aequitas1
Tufted Titmouse

Joined: 8 May 2013
Age: 38
Gender: Male
Posts: 41

11 May 2013, 1:24 pm

Ellingtonia wrote:

Somberlain wrote:

a) For 500: Odd wizards can give clue to even wizards by guessing closer numbers to their actual number.

Also subtracting numbers can eliminate ''over 1001'' problem for b).

Excellent.

Last edited by aequitas1 on 11 May 2013, 1:42 pm, edited 3 times in total.

aequitas1
Tufted Titmouse

Joined: 8 May 2013
Age: 38
Gender: Male
Posts: 41

11 May 2013, 1:28 pm

naturalplastic wrote:

Somberlain wrote:

a)
Also subtracting numbers can eliminate ''over 1001'' problem for b).

Is there a dope-slap emoticon?

That would just replace the 'over 1001 problem' with the 'no negative numbers problem"!

His answer was very innovative and clever but it has exceptions and where there are exceptions in this case there is uncertainty.

Somberlain
Deinonychus

Joined: 20 Jun 2012
Age: 38
Gender: Male
Posts: 362
Location: Land of Seven Horizons

11 May 2013, 1:41 pm

aequitas1 wrote:

Somberlain wrote:

a) For 500: Odd wizards can give clue to even wizards by guessing closer numbers to their actual number.

Also subtracting numbers can eliminate ''over 1001'' problem for b).

No problem in that?

Free hat: 1
First wizards hat: 3
Second wizards hat: 2

The first wizard can say 1 or 3, it does not matter. If the first wizard says 1: the second wizard can say 2 or 3. He will choose 2, since it is closer to 1. If the first wizard says 3: the second wizard can say 1 and 2. 2 again.

_________________
Aspie quiz: 158/200 AS AQ: 39 EQ: 17 SQ: 76.
You scored 124 aloof, 121 rigid and 95 pragmatic.

English is not my native language. 1000th edit, here I come.

Somberlain
Deinonychus

Joined: 20 Jun 2012
Age: 38
Gender: Male
Posts: 362
Location: Land of Seven Horizons

11 May 2013, 2:21 pm

naturalplastic wrote:

Somberlain wrote:

a)
Also subtracting numbers can eliminate ''over 1001'' problem for b).

Is there a dope-slap emoticon?

That would just replace the 'over 1001 problem' with the 'no negative numbers problem"!

Somberlain wrote:

For b): Why addition, not subtraction? The first wizard can subtract the smaller unknown from the greater one, solving the 1001 problem. However, that number will surely be some other wizards number. Poor him.

_________________
Aspie quiz: 158/200 AS AQ: 39 EQ: 17 SQ: 76.
You scored 124 aloof, 121 rigid and 95 pragmatic.

English is not my native language. 1000th edit, here I come.

Ellingtonia
Sea Gull

Joined: 9 Oct 2011
Age: 33
Gender: Male
Posts: 200

11 May 2013, 2:30 pm

I've just reread the question and noticed this wording:

aequitas1 wrote:

(b) Can 999 wizards be promoted with certainty?

I'm becoming convinced that the answer is "No", but I'm having trouble proving it without confusing myself.

The first wizard cannot get his correct with certainty, he has no way of knowing which number is missing and which is on his head. If we want 999 wizards to be correct with certainty it must be all the wizards except the first.

Similarly, the first wizard must guess one of the two numbers his could be. If he guesses another number, then he will be wrong and the wizard who's number he guessed will also be wrong, leaving only 998 wizards to possibly get it right.

The obvious first step for any wizard is to eliminate all the numbers in front of him and all the guesses previously made, leaving two choices. The wizard can then deduce that one of these numbers is the one on his head and one of these numbers was the unchosen possibility that the first wizard had. There needs to be some rule, or set of rules, that the first wizard follows that will help the others deduce which is which.

Lets say that the guess the first wizard makes is 'a', his unchosen possibility is 'b' and the number on the head of the wizard about to answer is 'c'. The answering wizard knows 'a', but doesn't know which of his possibilities is 'b' and which is 'c'

The answering wizard knows that when the first wizard looked at 'a' and 'b' he followed the rule(s) and chose 'a'. Let's say for the moment that if the first wizard had instead had 'a' and 'c' as his possibilities, he would have chose 'c' The answering wizard can use this to figure out his number.
e.g. a=10, the rule is to pick the smallest number and the possibilities for 'b' and 'c' are 5 and 15. If the first wizard was choosing between 5 and 10 he would have chosen 5, but he didn't and so he wasn't. He must have been choosing between 10 and 15, therefore b=15, c=5. The number on the hat of the answering wizard is 5.

But what if the rule says that when the first wizard chooses between 'a' and 'c' he still chooses 'a'? Then it is impossible to tell which is 'b' and which is 'c'.
e.g. a=10, the rule is still to pick the smallest number but the possibilities for 'b' and 'c' are 20 and 15. The first wizard was either choosing between 10 and 15 or 10 and 20, but either way he still would have chosen 10. It is impossible for the answering wizard to tell which is 'b' and which is 'c'.

So what we need is a rule that will make the first wizard choose one number (a) over another number (b), but choose every other number (all possible 'c's for each of the other 999 wizards) over 'a'. It needs to be one rule that works regardless of what numbers 'a' and 'b' are.

Let's say x, y and z are all numbers between 1 and 1001. If the first wizard's choices are x and y, then the rule needs to choose z over x and y. If the first wizard's choice are x and z, then the rule needs to choose y over x and z. If the first wizard's choices are y and z, the rule needs to choose x over y and z. I don't see how this is possible.

naturalplastic
Veteran
Veteran

Joined: 26 Aug 2010
Age: 69
Gender: Male
Posts: 35,189
Location: temperate zone

11 May 2013, 3:04 pm

Somberlain wrote:

naturalplastic wrote:

Somberlain wrote:

a)
Also subtracting numbers can eliminate ''over 1001'' problem for b).

Is there a dope-slap emoticon?

That would just replace the 'over 1001 problem' with the 'no negative numbers problem"!

Somberlain wrote:

Sorry.

aequitas1
Tufted Titmouse

Joined: 8 May 2013
Age: 38
Gender: Male
Posts: 41

11 May 2013, 4:08 pm

Somberlain wrote:

aequitas1 wrote:

Somberlain wrote:

a) For 500: Odd wizards can give clue to even wizards by guessing closer numbers to their actual number.

Also subtracting numbers can eliminate ''over 1001'' problem for b).

Odd and even in what assignment? Hat values or a cardinal assignment of wizards? This is very clever of you. I should have paid a closer look towards solving for 500. I knew initially that odd/even expressions were relevant but I didn't devote effort towards working out the structure of such a strategy employing odd/even values with respect to proximity. I became pinned by the allure of solving 999.

I'm trying to disprove your 500 wizard strategy here and I'm uncertain. A few things popped up that I'm mulling over still; if we're assuming the hat value assignment is random then wouldn't the probability distribution of correct guesses be odd or asymmetrical? Will the strategy follow the same, symmetric distribution of correctness under all configurations of assigned values resulting in 500 promotions? I feel like if there are successive, equidistant value configurations or clusters of odd/even hat values then it would shift this either above or below .5 (specifically 0, .5, or 1). Where did I go wrong? If this initial assumption is true then would correcting it in a manner wherein odd and even both employ a system of expression individually promoting .5 even and .5 odd be sound and certain? Am I wrong on this one? I'm trying to find the one scenario wherein your solution is excepted.

I will likely edit this post as I continue to try to find the one scenario wherein the absolute solution is excepted if at all possible. Forgive my lack of such ability.

Somberlain
Deinonychus

Joined: 20 Jun 2012
Age: 38
Gender: Male
Posts: 362
Location: Land of Seven Horizons

11 May 2013, 4:57 pm

aequitas1 wrote:

Somberlain wrote:

aequitas1 wrote:

Somberlain wrote:

a) For 500: Odd wizards can give clue to even wizards by guessing closer numbers to their actual number.

Also subtracting numbers can eliminate ''over 1001'' problem for b).

Odd and even in what assignment? Hat values or a cardinal assignment of wizards? This is very clever of you. I should have paid a closer look towards solving for 500. I knew initially that odd/even expressions were relevant but I didn't devote effort towards working out the structure of such a strategy employing odd/even values with respect to proximity. I became pinned by the allure of solving 999.

I'm trying to disprove your 500 wizard strategy here and I'm uncertain. A few things popped up that I'm mulling over still; if we're assuming the hat value assignment is random then wouldn't the probability distribution of correct guesses be odd or asymmetrical? Will the strategy follow the same, symmetric distribution of correctness under all configurations of assigned values resulting in 500 promotions? I feel like if there are successive, equidistant value configurations or clusters of odd/even hat values then it would shift this either above or below .5 (specifically 0, .5, or 1). Where did I go wrong? If this initial assumption is true then would correcting it in a manner wherein odd and even both employ a system of expression individually promoting .5 even and .5 odd? Am I wrong on this one? I'm trying to find the one scenario wherein your solution is excepted.

I will likely edit this post as I continue to try to find the one scenario wherein the absolute solution is excepted if at all possible. Forgive my lack of such ability.

I think there is a misunderstanding.

Odd wizards give clues, even ones answer correctly. By saying odd (or even) wizards, I mean their position in the line, not their hat number.

In other conditions, odd wizards would state the closer number to their even successors.

let me give an example to clarify the method.

The seventh wizard (odd) in the line will have two options, for example 274 and 16. In front, from eighth wizard he reads 982. Even wizard already knows that there are three missing numbers for him beforehand: 982, 274 and 16. At this point, he would state the smaller closer number, namely 274. If eighth wizards hat was 16, he would say 982. So it is in a circular manner (mod 1001). If he had said 982, he would be pointing 16. If he had said 16, he would be pointing 274 and 274 would be pointing 982.

I do not know if I managed to clearly state my thoughts.

_________________
Aspie quiz: 158/200 AS AQ: 39 EQ: 17 SQ: 76.
You scored 124 aloof, 121 rigid and 95 pragmatic.

English is not my native language. 1000th edit, here I come.

Last edited by Somberlain on 11 May 2013, 5:05 pm, edited 2 times in total.

eric76
Veteran
Veteran

Joined: 31 Aug 2012
Gender: Male
Posts: 10,660
Location: In the heart of the dust bowl

11 May 2013, 4:57 pm

Ellingtonia wrote:

I've just reread the question and noticed this wording:

aequitas1 wrote:

(b) Can 999 wizards be promoted with certainty?

The only way I can imagine to get 999 with certainty is if the first to guess provides both numbers he doesn't see by choosing a number in excess of 1001. For example, multiply one number by 10000 and add them together. Then the next knows what two numbers the first didn't see and can easily determine his own number by what number he doesn't see. And so on. But for that to work, the first wizard would have to be unconstrained from his choosing numbers only between 1 and 1001.

If he can choose numbers other than integers, he could provide both numbers by x+(y/10000) where x is the smaller of x and y. Then 1001 > x+(y/10000) > 1.

Suppose that wizard number X can accurately determine his hat and so that is his guess. Unless there is some absolute way that wizard number x+1 can know what numbers wizard x didn't see, there will be uncertainty and that wizard cannot positively guess his own number.

For 999 of them to accurately determine their own number without guessing, then the first will have had to find a way to indicate both numbers he didn't see. Similarly, for 998 of them to accurately determine their own number without guessing, then two of them will have to indicate three numbers that they didn't see. It can be the first 2 or the first and third.

Really, I don't see how one could get more than 500 correct hats with certainty.

trollcatman
Veteran
Veteran

Joined: 21 Dec 2012
Age: 43
Gender: Male
Posts: 2,919

11 May 2013, 5:25 pm

(a) Show that at least 500 wizards can be promoted with certainty.

The first wizard can guess right or wrong, 50% chance for either, since he knows 999 out of 1001. Strategy: 499 wizards will assume he guessed right, the other 500 will assume he guessed wrong.

(b) Can 999 wizards be promoted with certainty?

Only if #2 figures out whether #1 was right or wrong. How that works.. ehhmm... I'm too stupid to be a wizard at the Unseen University

Edit: after reading some the posts here I concluded too early about #2 having to know whether #1 was right. But I still haven't figured out if 999 is possible. Solving b takes a super-duper wizard.

Page 3 of 8 [ 114 posts ] Go to page Previous 1, 2, 3, 4, 5, 6 ... 8 Next

Jump to:

Excellent Math Riddle Post Reply New Topic

Excellent Math Riddle