An old Bob Kraus puzzle from MathPuzzle

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

thatsmyusername
Posts: 18
Joined: Wed Jan 27, 2010 1:04 pm UTC

An old Bob Kraus puzzle from MathPuzzle

Postby thatsmyusername » Wed Jan 27, 2010 1:06 pm UTC

http://www.mathpuzzle.com/krauspuz.html

3. MATH CLASS
A high school math teacher chose three of his best students to conduct a little experiment. He said, "I have chosen a three-digit number, N, with the first digit not more than the second and the second not more than the third. I also have chosen a function, F(N), which is one of these five functions:

(1) SUM(N) = The Sum of the digits of N.
(2) PROD(N) = The Product of the digits of N.
(3) SSQ(N) = The Sum of the Squares of the digits of N.
(4) SSC(N) = The Sum of the Cubes of the digits of N.
(5) LCM(N) = The Least Common Multiple of the digits of N.

"I then calculated the value, V = F(N), and have written the three items, N, F, V, each on a separate piece of paper and will give one to each of you. You must try to determine the other 2 items not on your paper. You may use your computers, but cannot collaborate. Don't turn in your answers until I ask for them. Don't worry about any unfair disadvantage of which item you get, this is not a competition, only an experiment. Just make your lists and we'll see what happens!"

Here is what happened:
1:00 - Students begin working.
1:20 - Teacher asks if anyone had found the answers. No one had.
1:30 - Teacher asks if anyone had found the answers. No one had.
1:31 - Teacher asks if it would help if he told them if N was odd or even. All 3 say no.
1:40 - Teacher asks if anyone had found the answers. No one had.
1:41 - Teacher asks if it would help if he told them if V was odd or even. All 3 say no.
1:50 - Teacher asks if anyone had found the answers. No one had.
1:51 - Teacher asks if it would help if he told them the sum of N and V. All 3 say no.
2:00 - Teacher asks if anyone had found the answers. All three of them had!


Can anyone solve this puzzle?

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Tirian » Wed Jan 27, 2010 6:08 pm UTC

The first puzzle is tractable.

Spoiler:
3479


The fact that no reader of Mathpuzzles.com solved the final puzzle makes me reluctant to put the time into it. In theory it's the same process, but I'm not completely confident of how to parse "if it would help".

ETA: And now that I've put some time into it, it looks even more poorly defined than I had originally suspected. I'm really pretty surprised, coming from Robert Kraus and Ed Pegg, Jr.

thatsmyusername
Posts: 18
Joined: Wed Jan 27, 2010 1:04 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby thatsmyusername » Thu Jan 28, 2010 1:49 am UTC

You nailed my problem exactly. I'm not sure what their rejection for additional helpful hints mean either. I tried 2 different interpretations, and neither work.

I actually just e-mailed Ed about whether anyone solved the puzzle, and possibly resurrecting it, etc. We'll see how he responds.

I don't know how to contact Robert Kraus. His geocities site is down, but Wayback Machine still has a mirror (http://web.archive.org/web/*/http://www ... zzles.html). All my e-mail attempts bounced.

I'm not sure what the policy is regarding cross-linking to other forums, but someone at GL claimed to have found a solution.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Tirian » Thu Jan 28, 2010 3:18 am UTC

Oh, good for you. I thought about emailing Ed, but then decided against it.

I didn't mention the other qualm I have, which is whether 0 is supposed to be a legal digit. It seems like it would be, because the digits are described as decreasing instead of increasing and zero was specifically excluded in the first problem on that page, but then how would you define the LCM? So I just assumed that the digits had to be 1-9 with misgivings.

I can wrap my mind around the fact that there may be a solution for some reading of the problem.

Spoiler:
At the end, the people who know N and V=F(N) agree that knowing N and V they couldn't tell what F is. That's a pretty narrow constraint. By my count, you're down to 55 possible cases including three pairwise relatively prime numbers, 333, 633, 642, and 963. But then they seem to learn from the fact that the other person feels the same, so maybe something like 321 and/or 611 seems like a potentially promising avenue.


But even so, it would still be a deeply unsatisfying problem, which is why I didn't feel like investigating that deeply...

Spoiler:
... because until then, there is no reduction in the number of potential cases beyond the initial drop from 825 to 625 cases. This is with the most liberal reading of "help" that I can believe, which is "is it possible that telling you the answer would allow you to tell me all three numbers immediately?" The only thing that would be more liberal is "Do you know the answer to this question already?", but of course then the poor kid who only knows F would never turn down a hint. But I don't believe that Robert Kraus would come up with a puzzle that had all these rounds that didn't get used, so I'm back to my initial assumption that I don't understand the ground rules.

thatsmyusername
Posts: 18
Joined: Wed Jan 27, 2010 1:04 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby thatsmyusername » Thu Jan 28, 2010 4:44 am UTC

Yep, again you pretty much summed me up. Heck, even before we encounter the whole "help" semantics, I'm still not sure why Robert made the teacher question them at 1:30. There's no way any of them can have an answer at that point, so it seemed like a wasted round to me, with absolutely no new information generated.

freddyfish
Posts: 69
Joined: Sat Oct 20, 2007 3:08 am UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby freddyfish » Thu Jan 28, 2010 4:50 am UTC

isnt this just something like
Spoiler:
there are a finite number of cases. List them all. Take the value you know and eliminate the cases that are not the same. look down the list. It does not help you to know if the first thing offered is odd or even. it doesnt help anyone else. eliminate all the cases that would help. repeat for teh second value. for teh correct values, there should only be one case left.

isnt this just a more complex variation of the problem with the tax collector and the hint that there is an older kid or something?

thatsmyusername
Posts: 18
Joined: Wed Jan 27, 2010 1:04 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby thatsmyusername » Thu Jan 28, 2010 4:55 am UTC

Yes, the process is obvious, but in the context presented, even with plugging in several different definitions of "help", the process does not lead to a unique solution.

Ermes Marana
Posts: 44
Joined: Sun Feb 08, 2009 12:20 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Ermes Marana » Thu Jan 28, 2010 6:48 am UTC

I don't think this is a possible sequence of events. Specifically, I do not believe it is possible that the student who knows the function can be sure the sum N + V will not immediately give him the solution.

Spoiler:
Say you know the function is PROD. It is plausible to you that the numbers are N = 111 and V = 1. For the two who do not know the function, even being told this N and V is not sufficient to decide if the function is PROD or LCM. But if you are the function guy, you can't be sure the sum won't be N + V = 112, in which case you would know both numbers and the function. The same thing happens if you know the function is LCM.

Now suppose you know the function is SUM (or SSQ or SSC). It is plausible to you that the numbers are 111 and 3. Again, even being told both these numbers would not help the others figure out the function. But if the sum comes back N + V = 114, then you have the solution.

So in any case, if you know the function then there is a certain sum which would give you the complete solution, and you can't be sure that sum won't be given to you.

I am assuming here that 111 is the smallest allowed number N, but given the use of LCM I don't see an alternative.

User avatar
phlip
Restorer of Worlds
Posts: 7565
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: An old Bob Kraus puzzle from MathPuzzle

Postby phlip » Thu Jan 28, 2010 6:59 am UTC

Ermes Marana:
Spoiler:
So therefore the function must be one that the person holding the function can rule out N=111 at some point during the first 6 steps.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Gopher of Pern
Posts: 250
Joined: Fri Jan 15, 2010 1:28 am UTC
Location: Central Coast, Australia

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Gopher of Pern » Thu Jan 28, 2010 10:36 pm UTC

thatsmyusername wrote:Yep, again you pretty much summed me up. Heck, even before we encounter the whole "help" semantics, I'm still not sure why Robert made the teacher question them at 1:30. There's no way any of them can have an answer at that point, so it seemed like a wasted round to me, with absolutely no new information generated.


The reason he asked them again is because the students had new information from last time: The other students could not work it out just from their paper alone. This would remove some possibilities from the table.
Look In My Face
Stare In My Soul
I Begin To Stupefy

thatsmyusername
Posts: 18
Joined: Wed Jan 27, 2010 1:04 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby thatsmyusername » Thu Jan 28, 2010 11:22 pm UTC

I understand the process, like I said. Of course, there's a "fixed point" where asking the same question again will not generate new information (which is why the teacher offers additional help with different types of questions). What I was arguing is that after the question at 1:20, this fixed point was already reached (625 possibilities as Tirian pointed out), and asking the same question again at 1:30 is pointless.

I suggest that others actually work out the puzzle in this specific scenario to better understand why Tirian and I are frustrated by it.

User avatar
phlip
Restorer of Worlds
Posts: 7565
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: An old Bob Kraus puzzle from MathPuzzle

Postby phlip » Thu Jan 28, 2010 11:51 pm UTC

Possible 169-ey interpretation:
Spoiler:
a couple of the questions are only one minute apart... that wouldn't give the students a whole lot of time to figure out the implications of the other students' answers to the previous question, before they're asked the next one. Perhaps their answers to the questions at 1:31, 1:41 and 1:51 don't take into account information from the answers at 1:30, 1:40 or 1:50, respecitvely?

Is it solvable if you do that?

But then, they do have one minute, which is more than nothing... maybe that'd be enough to cross off the most obvious of possibilities, but might not be enough to do a thorough search... but then, we don't know how fast they work, and we don't know if this speed is common knowledge among the three... but I think I'm overcomplicating this.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

thatsmyusername
Posts: 18
Joined: Wed Jan 27, 2010 1:04 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby thatsmyusername » Fri Jan 29, 2010 12:07 am UTC

A discussion from GL actually shed a very important light. The person holding a number may not know whether he's holding N or V.

A value of V=226, for example, uniquely identifies N=899 and F=SSQ. However, a person holding a number 226 at 1:00 does not know if that number is V or N, and therefore would not have been able to solve the puzzle at 1:20.

The number of possibilities left at 1:25 therefore is not 625.

With this new realization, I may now be able to solve the puzzle. Let me work on it some more.

thatsmyusername
Posts: 18
Joined: Wed Jan 27, 2010 1:04 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby thatsmyusername » Fri Jan 29, 2010 12:56 am UTC

Oh, by the way, in case you're wondering, Bob Kraus did design this puzzle with computer help in mind. He suggested use of spreadsheet program. A person in GL used Java. I use Maple.

The reason I point this out is: (i) to encourage someone to actually execute the (tedious-by-design) process with help of computer (ii) to ask if others know of other logic puzzles with similar design philosophy. I really enjoyed what Bob Kraus called his "meta-puzzles", and I'm just wondering if there are others like it out there.

Ermes Marana
Posts: 44
Joined: Sun Feb 08, 2009 12:20 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Ermes Marana » Fri Jan 29, 2010 1:50 am UTC

thatsmyusername wrote:A discussion from GL actually shed a very important light. The person holding a number may not know whether he's holding N or V.


Along the same lines... notice that the functions are numbered.

Maybe the person getting the function only gets the number of the function. If so:

Spoiler:
I think N=111, F=3, V=3 is a solution.

By the same logic as in my last post, anyone with a 1,2,4, or 5 would have to say yes at 1:51, because a sum of 112 or 114 would give them the solution. If everyone says no they can all conclude that there are two 3's out there, in which case by 2:00 they all have the solution.

thatsmyusername
Posts: 18
Joined: Wed Jan 27, 2010 1:04 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby thatsmyusername » Fri Jan 29, 2010 1:54 am UTC

Dear god this problem is a mess!

Tirian, I don't know your relationship with Ed, but could you e-mail him anyway? If he sees more people interested in this problem, maybe he has more reason to resurrect it.

thatsmyusername
Posts: 18
Joined: Wed Jan 27, 2010 1:04 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby thatsmyusername » Fri Jan 29, 2010 4:23 am UTC

OK I'm going to detail how far I'd get if:
- I assume that envelopes are clearly labeled (so to speak)
- A hint is only "helpful" if it allows them to immediately single-out the solution

After 1:00 - 825 possibilities
After 1:20 - 625 left, 200 removed because V would've solved it
After 1:30 - 625 left ("wasted" round)
After 1:31 - 585 left, 40 removed because V + hint would've solved it
After 1:40 - 584 left, [899, LCM, 72] would've been solvable by N
After 1:41 - 572 left, 12 removed because N + hint would've solved it
After 1:50 - 572 left ("wasted" round)
After 1:51 - 113 left (374/180/204 would've been solvable by N/F/V + hint)

Among these 113, no unique value in N, F, or V.

Comments?

User avatar
Gwydion
Posts: 336
Joined: Sat Jun 02, 2007 7:31 pm UTC
Location: Chicago, IL

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Gwydion » Fri Jan 29, 2010 4:44 pm UTC

Agreed, those assumptions lead to no solution, but my opening assumptions were different -

1) The players have a sheet of paper with a number written on it
2) They do not know if their number is N, V, or F (the number 1-5 corresponding to the function given above)
3) A hint is "helpful" if there exists an answer to the question by which they would know all 3 numbers
- In other words, if knowing N was odd they could narrow down the choices to a single unique set {N,F,V}, then that hint would be helpful, even if knowing N was even would not narrow things down.

I'll work on it more later and get back to you guys

Edit: Also, reread the OP - the digits of N are such that the first is not more than the second and the second is not more than the third... Meaning they're in ascending, not descending order

thatsmyusername
Posts: 18
Joined: Wed Jan 27, 2010 1:04 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby thatsmyusername » Fri Jan 29, 2010 10:42 pm UTC

Technically the digits are in "non-descending" order. "Ascending" is often interpreted more strictly (e.g. 007 is "non-descending", but it's not "ascending", I think...).

I do think that Tirian skipped a word when he said that the digits are decreasing. I think he meant to say non-decreasing.

Ermes Marana
Posts: 44
Joined: Sun Feb 08, 2009 12:20 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Ermes Marana » Sat Jan 30, 2010 3:36 am UTC

I looked at past updates of the original site, and this puzzle was deleted from the page on the most recent update. The rest of the puzzles on the page stayed the same.

Perhaps the author realized the puzzle had no solution given the most reasonable interpretation (that the students saying "no" means they are 100% sure the information cannot help them).

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Tirian » Sat Jan 30, 2010 1:43 pm UTC

Nope. Gwydion's point is well-taken. I misread it. So it is clear that 0 is not to be a digit, which is a small comfort.

Anyway, I am satisfied that Robert Kraus came to understand that this puzzle was troublesome, but never got word to Ed to take it out of mathpuzzle.

User avatar
Cosmologicon
Posts: 1806
Joined: Sat Nov 25, 2006 9:47 am UTC
Location: Cambridge MA USA
Contact:

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Cosmologicon » Fri Feb 05, 2010 4:23 pm UTC

thatsmyusername wrote:OK I'm going to detail how far I'd get if:
- I assume that envelopes are clearly labeled (so to speak)
- A hint is only "helpful" if it allows them to immediately single-out the solution...

Among these 113, no unique value in N, F, or V.

Comments?
The problem is *much* harder than you're thinking, if you think a hint only matters if it allows them to immediately single-out the solution. In order to fully analyze the problem as written, you need to track not only what A, B, and C know about the possibilities at any given time, but also what A knows about what B knows, what A knows about what C knows, what B knows about what A knows about what B knows about what C knows, and so on. Like the blue-eyes problem with 100 levels of indirection, I think this one requires up to 7 (or at least 4) levels of indirection by the end.

I find it difficult to believe that this could be solved with a spreadsheet, though, so maybe that's not what the puzzle writer intended.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Tirian » Fri Feb 05, 2010 6:04 pm UTC

It's not as horrible as you make it out. The first problem that is on that page (which I reproduce here) has the same indirect self-awareness that troubles you, but is quite solvable. I used a half-page Python script myself, but in theory I can see how you could do the work in a spreadsheet.

A wealthy man had three sons all of whom were quite good at math and logic. To get a share of his inheiritance each had to correctly determine a positive integer which he had chosen. He told them that the number had four different non-zero decimal digits, in ascending order.

He prepared three sealed envelopes each of which contained a number. The first contained the product of the four digits, the second contained the sum of the squares of the four digits, the third contained the sum of the product of the first two digits and the product of the last two digits, and the envelopes were clearly marked as such. He showed the three envelopes to the three sons and had them each take one at random.

The sons were stationed at three different computers so that they couldn't communicate with one another (but were linked to the father's computer). After one hour they could submit a number or decline. Anyone who submitted a wrong answer would be eliminated and get nothing. If one or more submitted the correct answer they would each receive a share of the inheritance, and the contest would end with the others getting nothing. If no one submitted the correct answer they would be instructed to work on the problem for another hour. The process would repeat as often as necessary.

At the end of the first hour no one had submitted an answer.
At the end of the second hour no one had submitted an answer.
At the end of the third hour no one had submitted an answer.
At the end of the fourth hour all three of them submitted the correct answer!

Can you determine the number?


To be pedantic, I'd add in the rule that the sons will only submit an answer if they are certain that it is correct. If at any time the sons reasoned that their father would deliberately choose a fair logically-based challenge instead of one that rewarded the person who got a key envelope, they'd be able to claim the prize earlier.

thatsmyusername
Posts: 18
Joined: Wed Jan 27, 2010 1:04 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby thatsmyusername » Thu Feb 11, 2010 1:26 am UTC

My solution to the Inheritance Envelope problem in Maple is about 23 lines with generous formatting.

Code: Select all

F := [
  L -> L[1]*L[2]*L[3]*L[4],
  L -> L[1]^2 + L[2]^2 + L[3]^2 + L[4]^2,
  L -> L[1]*L[2] + L[3]*L[4]
]:

filter := (S, pred) -> map(m -> `if`(pred(m), m, NULL), S):

mapMultiset := (f, pos) -> {op(
  convert(map(f, [op(pos)]), multiset)
)}:

singles := (f, pos) -> filter(pos,
  p -> member([f(p), 1], mapMultiset(f, pos))
):

allSingles := (pos) -> op(map(singles, F, pos)):

pos := {op(combinat[choose](9, 4))}:
pos := pos minus (`union`(allSingles(pos))):
pos := pos minus (`union`(allSingles(pos))):
pos := pos minus (`union`(allSingles(pos))):
sol := `intersect`(allSingles(pos)):

User avatar
Aardvarki
Posts: 129
Joined: Tue Jul 17, 2007 3:51 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Aardvarki » Wed Mar 10, 2010 6:16 pm UTC

I know this is an old post and most people have given up on it - but I just found it and i really like this puzzle!

First, some thoughts of mine on the subject:
1: The meaning of asking the students if "it will help", I agree that this must mean "will any possible answer I give unambiguously solve the problem for you". If it were to mean "will any possible answer I give remove any possibilities", there is no way all three students would answer 'no' each time.
2: I agree with the consensus that N is a non-decreasing three digit number with digits 1-9 (no zeroes). This gives 165 possible N values, or 825 possible solutions to start with.
3: I believe the cards the students receive are UNLABELED (the student can only use their intellect to determine whether they have been given N,F, or V) and that the values for F are 1-5, each denoting one of the formulae.


Now some observations:

Ermes: Your solution of 111,3,3 cannot work because at the third questioning, if one team is holding a 3, they will answer YES - a V+N of 336 will tell them for certain that the solution (N,F,V) is 333,5,3.

Based on this same logic, no team can be holding a 4, as if they are holding a 4, they will also answer YES to the third question - if the V+N is 248, they will know the answer (N,F,V) is 244,5,4 as all of the other valid V+N=248 would not allow for anyone to hold a 4.

As well, no team can be holding a 5, because if they are they will answer yes - if V+N is 160, they will know the answer is 155,5,5.


Here's my knockouts for each round of questioning:
Spoiler:
Start - There are 825 unique possible solutions
1:20 - no students have the answer, therefore all solutions with unique V values are eliminated (ex: 128,4,521 is removed because this is the only solution with V=521, HOWEVER 227,4,359 is NOT removed here, because while this is the only solution with V=359, there exist solutions where N=359 still, so the person with the 359 card would not know whether they are holding N or V)
1:30 - eliminating all of the unique Vs does not actually eliminate any further possibilities, this round of questioning gets us nowhere.
1:31 - all students answer 'no' to whether knowing N is even/odd will help, therefore all Vs that are unique among the set of all solutions where N is even and all Vs that are unique among the set of all solutions where N is odd are removed. (ex: 128,3,69 is removed here because V=69 is only valid in 128,3,69 and 247,3,69, and knowing whether N is even or odd will give us the solution)
1:40 - "wasted round"
1:41 - all students answer 'no' to whether knowing V is even/odd will help, therefore all Ns that have only one remaining odd or even V value are eliminated. (ex: we will remove N=128 entirely at this point because the only three valid N results are 128,1,11; 128,2,16; and 128,5,8 - the team holding 128 would answer YES to this question, because hearing the V is odd would give them the solution)
1:50 - "wasted round"
1:51 - all students answer 'no' to whether knowing V+N would help, you can remove a LOT of solutions from this - anything where F=3,4,5 is eliminated, because anyone holding one of these numbers would have answered YES, also any N where a possible N+V would reveal the solution (ex: N=117 is removed entirely because the person holding 117 would have answered YES, because if N+V=462, they would have known the answer was 117,4,345 as N+V=462 is unique to that solution).
2:00 - The students all know the answer! This means that one of the remaining solutions is unambiguous for all three students.


I'm currently eliminating the possibilities for the last step, I'm stuck with about 20 possible solutions and am trying to figure out what i'm missing.

Anyone else make any progress?
-Aa
Weeks wrote:The only Dexter I really know is the one with the lab

User avatar
Aardvarki
Posts: 129
Joined: Tue Jul 17, 2007 3:51 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Aardvarki » Wed Mar 10, 2010 6:28 pm UTC

New thought!

Spoiler:
No one can be holding a 2 card either. If anyone is holding a '2' during the last question, they will answer 'YES' because if N+V = 124, they will know the solution is (122,5,2).

There do exist two solutions with a '2' card where N+V = 124, however the other (117,2,7) is eliminated during the first round of questioning, because if someone were holding a '7' card during the first round of questioning, they would answer YES, because finding out that N is even would solve the problem (124,1,7).

Therefore, F=1.

As for N and V, I'm working on it!

(edit: For clarification, all of my solutions are in the format (N,F,V))
-Aa
Weeks wrote:The only Dexter I really know is the one with the lab

epok88
Posts: 10
Joined: Sat Nov 28, 2009 6:01 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby epok88 » Wed Mar 10, 2010 10:10 pm UTC

do they know what's on their paper? eg: do the papers say N=984 or just 984?

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: An old Bob Kraus puzzle from MathPuzzle

Postby jestingrabbit » Thu Mar 11, 2010 1:29 am UTC

I think everybody is assuming the later ie they have a number, they don't know what the number represents.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Nix
Posts: 93
Joined: Mon Mar 09, 2009 8:14 am UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Nix » Thu Mar 25, 2010 10:17 am UTC

I've only just started working on this. 825 is repeatedly mentioned as the initial number of possibilities, but I'm getting 824. If I treat (244, 4, 136) as different from (136, 4, 244) I get 825 as well. Surprisingly, that is the only set of numbers that works in more than one permutation, apart from those with F=V.

Note that the students are expected to tell what numbers the others have, not how they originated. Maybe you have already taken this into account elsewhere, maybe this will help. Or am I looking at things wrong?

Edit: Obviously this depends on how you define "possibilities", and I'm counting sets of numbers instead of full world configurations (including which one is N and which one V). In this case that difference actually shouldn't even be visible since the parities and N+V are the same for either case. Anyway, this still needs to be taken into account at some point, I think.

User avatar
BigNose
Posts: 72
Joined: Thu Feb 18, 2010 2:45 pm UTC
Location: Swine's Down, UK

Re: An old Bob Kraus puzzle from MathPuzzle

Postby BigNose » Thu Mar 25, 2010 3:21 pm UTC

Excuse me, but maybe I am feeling thick, but according to the rules of the experiment:
I have chosen a three-digit number, N, with the first digit not more than the second and the second not more than the third.

To me this states that (assuming that the 1st digit is hundreds etc) just by following this rule, only 165 numbers exist from 100 to 999, starting at 111-119 and ending with 888, 889, 899 & 999.
Please tell me I have the right understanding, before I spend too much time on this!
If so, I have further ideas how to 'solve' this (by 'solve' I hope to mean 'gain a single answer', slthough it may work out to be 'it's a choice of this, this or this).
ta
Adacore wrote:In all honesty, BigNose has been pinging me slightly with almost every post since the start of the game. But he always does - I was utterly convinced he was anti-town for most of Wizardry2 and he was the High Wizard. I just can't read him.

Nix
Posts: 93
Joined: Mon Mar 09, 2009 8:14 am UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Nix » Thu Mar 25, 2010 6:13 pm UTC

BigNose wrote:To me this states that (assuming that the 1st digit is hundreds etc) just by following this rule, only 165 numbers exist from 100 to 999, starting at 111-119 and ending with 888, 889, 899 & 999.

Correct. At least that seems to be how everyone is reading it.

Nix
Posts: 93
Joined: Mon Mar 09, 2009 8:14 am UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Nix » Fri Mar 26, 2010 11:16 am UTC

I'm stuck. I've tried all interpretations I can think of, with no solution.

Spoilered the analysis just in case.

Spoiler:
The options are:
  • The numbers given to the students are A) all unlabeled with F expressed as a number 1..5, B) N and V unlabeled but F different, or C) all labeled.
  • Saying "information Z would not help" means that X) no possible variant of Z would make the answer unique, or Y) not all possible variants of Z would make the answer unique.

For X it seems that someone would always say yes to "would N+V help?" regardless of choosing A, B or C.

For Y, I can't get anyone to solve the problem in the end, never mind all of them. The number of possible sets of numbers after the N+V question is A: 169, B: 119, or C: 113. If I ignore the consideration that took the initial number from 825 to 824 in A and B, I get A: 177, or B: 132.

Does someone get different results for some set of assumptions, or are there even more ways to read the question?

If that isn't the case and I haven't made mistakes, maybe working things out from just the common knowledge isn't enough and we need to consider things like "student a knows that student b knows that student a knows that student c knows that x", like Cosmologicon mentioned, in order to solve this. That could even fix the odd second question that never removes any options. I'm not sure how to approach solving the puzzle in reasonable time, though.

Edit: The state space isn't that huge after all, since we need to consider about 8 levels deep and the tree is only binary (e.g. c can consider the knowledge of a and b) for a total of 256 leaves. I'll see where that goes next, if no one has any better ideas.

Jsty
Posts: 10
Joined: Thu Feb 05, 2009 4:35 am UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Jsty » Mon Mar 29, 2010 10:51 am UTC

Can anyone solve this puzzle?


Why yes! That's the beauty of logic puzzles!

Should you be curious, I managed to deduce this:
1:00 - 165 possible solutions
1:21 - 101 possible solutions
1:31 - 24 possible solutions
1:41 - 12 possible solutions
1:51 - 12 possible solutions
2:00 solved.

I truly wouldn't want to spoil it!
Spoiler:
Thankfully, we have the luxury of starting with the finished solution, which makes this considerably easier, although you may choose to brute-force through the front end of the puzzle too.
I chose to do the latter as well, and only swept it up from the back end to confirm my logic.

Ermes Marana
Posts: 44
Joined: Sun Feb 08, 2009 12:20 pm UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Ermes Marana » Mon Mar 29, 2010 3:10 pm UTC

As you figured, there is no solution for the reasonable interpretation of the problem (that the students say the information will not help them only if they can deduce that the information will not help them).

However, if you assume that the students magically know whether the information would help them or not, then you can solve it.

Nix
Posts: 93
Joined: Mon Mar 09, 2009 8:14 am UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Nix » Thu Apr 01, 2010 11:32 pm UTC

Ermes Marana wrote:However, if you assume that the students magically know whether the information would help them or not, then you can solve it.

Does the magical knowledge work the same way as if the questions were simply replaced with such like "If I told you that N was even, would you know the answer?" matching the actual values of N and V, or do you mean something else?

I don't get results for any possibly valid combination of such questions (and choice of labeling scheme), but my code is growing complex (possibly buggy) and I don't feel like checking its work by hand. Will do that though if you can confirm the above.

You could also post the correct interpretation of the number labeling (A, B or C in my previous post) if not the actual sequence of questions or even the correct numbers. That's if you actually have this solved and aren't just guessing at how it could be.

Jsty, you could also show some of your work, at least tell us how to interpret the puzzle. I can't make sense of your spoiler, and 165 possible solutions at 1:00 sounds weird.

By the way, I didn't code any of the nested meta-knowledge solution. That's because I can't see how the set of possible worlds someone at any level of nesting considers, would at any point differ from ones calculated from the common knowledge of overall possible worlds and the person's own number. If that's true, how else could that complicated way of thinking contribute to solving the puzzle?

User avatar
BigNose
Posts: 72
Joined: Thu Feb 18, 2010 2:45 pm UTC
Location: Swine's Down, UK

Re: An old Bob Kraus puzzle from MathPuzzle

Postby BigNose » Thu Apr 08, 2010 3:11 pm UTC

Haven't looked at this for a while, but here is some (obvious) think-ons:

Who ever has F, knows they do not have N
Who ever has N, knows they do not have F
Any value provided between 6 and 110 must be V
Any value exceeding 999 must be V

Does V gain any advantage by knowing (through the logic above) that they have V?

Telling them that the 'parity' of N is ODD and that 'parity' of V is EVEN and that N+V=?? - will help them.
What I mean is that the 'parity' will restrict N+V values whereby only 1 combination of N and V's parity will produce a single result.
Adacore wrote:In all honesty, BigNose has been pinging me slightly with almost every post since the start of the game. But he always does - I was utterly convinced he was anti-town for most of Wizardry2 and he was the High Wizard. I just can't read him.

Nix
Posts: 93
Joined: Mon Mar 09, 2009 8:14 am UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Nix » Fri Apr 09, 2010 12:45 am UTC

Trying to solve this puzzle as usually interpreted seems futile. Many have tried, even with computer programs, with the result of "it's impossible". Unless the two claimed solvers come up with something to back their claims, or we can think of new ways to interpret it, this puzzle seems like a waste of time.

I've tried a whole bunch of variations with my program, no results. These are the variables:
  1. Defining the value of a concrete piece of information like "N plus V is 112". A student would consider the given piece of information to help iff given it, { (A: there would be a single answer), or (B: some of the currently possible answers would be eliminated) }.
  2. Defining how the students would answer to "would it help if I told you X", with X like "N plus V" for example. A student would say yes, iff { (A: any concrete variant of X), (B: all concrete variants of X), or (C: the actual concrete variant of X [by "magical knowledge"]) } would help according to the definition chosen above.
  3. Defining how the numbers are "labeled". If F is indistinguishable from N and/or V, it is given as a number 1..5. { (A: all three indistinguishable), (B: N marked, but F indistinguishable from V), (C: F marked [or not expressed as a number], but N indistinguishable from V), (D: V marked, but N indistinguishable from F), or (E: all three marked, or each recipient otherwise knows which one they got) }.
  4. Stretching the definition of a three-digit number to allow zeroes. The possible values for N are the otherwise allowed subset of { (A: 111..999), (B: 000..999), or (C: 000..999 where LCM(N) is defined, as defined below) }.
  5. Defining LCM(N) if N includes zeroes. If LCM(N) is undefined, F simply can't be LCM with that N. { (A: undefined), (B: LCM(000) = 0; else undefined), (C: LCM of the non-zero digits; LCM(000) = 0), or (D: LCM of the non-zero digits; LCM(000) is undefined) }.
  6. Defining how the inclusion of zeroes effects the "labeling". { (A: the leading zeroes in N are printed, i.e. if N has leading zeroes, N is recognizable from F and V), or (B: the leading zeroes in N are omitted, i.e. the regular labeling applies and N may be indistinguishable) }.
  7. Altering the digit relation rules of N, guessing possible error in the puzzle with the complicated expression. With N="xyz", i.e. 100x + 10y + z (with x y z in 0..9), x y z are restricted by: { (A: x<=y<=z), (B: x<y<z), (C: x>=y>=z), or (D: x>y>z) }.
  8. Adding a constraint for V. { (A: the puzzle stands as stated), (B: V must be a three-digit number), or (C: V must satisfy the same constraints as N) }.
I've examined almost all combinations of the above. The excluded ones combine 2C (the magical knowledge) with stretching the puzzle definition by more than one of (not 4A), (not 7A), (not 8A).

There is one combination that does produce some answers: 1A, 2C, 3A/C, 4A, 7A, 8B. 3A and 3C are equivalent because with 8B, N and V are distinguishable from F anyway. Out of 270 total possibilities, there are 6 working answers to the puzzle. 2C produces multiple answers in many combinations I excluded as well. Of the excluded more exotic combinations, some do have an unique answer, but truth be told, I don't like 2C one bit, and combining it with many obvious distortions of the puzzle just goes too far.

Of course it's always possible that I have a bug somewhere. I'd always welcome someone checking my results. Else we need even more stretching of the puzzle interpretation than I have applied. I may have missed something much more likely than my weirder scenarios. Any ideas?

If someone writes the same kind of program to verify my work, it would be useful to compare some of the intermediate numbers. That would work towards verifying both programs, as the same overall result of no working combinations doesn't tell all that much. PM me if you'd like some data to compare to.

I just had an interesting thought. In all of my calculations I've assumed that all the rules are common knowledge. That doesn't necessarily have to be true. For example, what if the students don't know which of the number labeling schemes is in use? The most likely example: F is given as the function and not a number, but the receivers of N and V don't know that. This is a bit harder to simulate, I will have to think about it. It would be one evil puzzle, and quite unlikely, but the analysis just isn't comprehensive without considering the possibility.

Another extension I thought about: Maybe 1 and 2 need to be chosen independently for the different questions. That would be weird if it's intentional and just forgotten out of the puzzle, but I think it's well possible that the author consistently made this mistake when checking their solution. "If N/V was odd or even" feels quite different from "the sum of N and V" after all. I'll add this possibility when I next get into this.

Edit: No solutions with the last addition, although I had to exclude more of the weird combinations when there are some Cs in 2, to limit the run time.
Last edited by Nix on Mon Apr 12, 2010 6:25 pm UTC, edited 1 time in total.

Jsty
Posts: 10
Joined: Thu Feb 05, 2009 4:35 am UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Jsty » Sun Apr 11, 2010 4:27 am UTC

1:00 - 165 possible solutions
Spoiler:
Well, I started with the given requirement that a <= b <= c, and calculated all possible numbers N could be, which is the 165 solutions I started with.

1:21 - 101 possible solutions
Spoiler:
Once everyone knew that nobody else had an immediate solution, they are left to deduce that nobody knows which function to use. I removed any solutions which only have one possible function. This left 101 possible options.

1:31 - 24 possible solutions
Spoiler:
Still though, because nobody has a solution, the person with a N can't decide if it's a N or a V, and visa versa. I removed any solutions which must be specifically N or V. i.e. if N were 999, then V would be 2187, and since the only possible F that exists is the 4th one ... somebody would have figured it out. Removing the unique F(N) or the N's that had a telltale V leaves 24 possible solutions.

Spoiler:
At this point, they're offered the choice to know whether N is odd or even. This would only help N if he knew that V was different than N, and visa versa, so I removed the options (of the 24 left), which leaves 12 possible solutions. There's a non-even playing field here, with fewer options being odd, and more options being even.

1:41 - 12 possible solutions
Spoiler:
Still, they haven't figured out which one exists, and suddenly they're given the option of knowing whether V was odd or even. This meant that there was the possibility that there was only one odd option, or only one even option. I selected the side with multiples. Still, I don't know how this was supposed to simplify things, or whether I looked too thoughtfully at the prior step. I imagine this would also reduce options if you were looking at the functions, but I didn't do that.

1:51 - 12 possible solutions
Spoiler:
At this point the teacher asks if it would help to give them the sum of N and V. The problem though, is that for any solution which has a comparable N and V, there's more than one F, so they can't immediately know the answer.

2:00 solved.
Spoiler:
Well, that means that there is one F which lets N be a solution of F(V), and V be a solution to F(N). So everyone knows each of F, V, and N now.


Now, I apologize if there's too much information here -- I invariably click the spoiler, and ruin the fun of finding things out myself. I also apologize if there's not enough here to explain my logic, or if my logic is fallible.

Good luck!

Nix
Posts: 93
Joined: Mon Mar 09, 2009 8:14 am UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Nix » Mon Apr 12, 2010 6:10 pm UTC

Thanks for explaining, Jsty! Hope you can clarify something.

Jsty wrote:1:00 - 165 possible solutions
Spoiler:
Well, I started with the given requirement that a <= b <= c, and calculated all possible numbers N could be, which is the 165 solutions I started with.

Spoiler:
165 different values of N, but how is that 165 solutions? For each N there are 5 possible values of F (and V follows). Counting just the different Ns makes it hard to follow your solution.

Jsty wrote:1:21 - 101 possible solutions
Spoiler:
Once everyone knew that nobody else had an immediate solution, they are left to deduce that nobody knows which function to use. I removed any solutions which only have one possible function. This left 101 possible options.

Spoiler:
Can you give an example of a solution that only has one possible function? I don't think I get what you mean.

As I think of it, there are some values of V that can only come from one pair of (N, F) and that the holder knows they can't be N (or F) instead *. The corresponding (N, F) pairs are eliminated here. Other than that, any N can still have any F, no? The holders of N and F can't know each other's number as they are totally independent before the question.

Are there really 64 values of N that are eliminated with all values of F? Intuitively it feels way too much, and a quick, possibly erroneous check tells me there would be no such Ns at all. Even if 64 were actually eliminated, the (N, F) pairs that were eliminated from other Ns can't be ignored either in the rest of the solution. Or are you counting something else than just the possible values of N here?

(*) I assume you're treating the problem like the students don't necessarily know if they have N or V at the start, because you're later using "the person with a N can't decide if it's a N or a V".

I'll look more carefully at the rest of your steps if you can help me understand this far.

Even if your solution is wrong like I think, I would like to understand it in case it's the same way the author "solved" the puzzle.

Jsty
Posts: 10
Joined: Thu Feb 05, 2009 4:35 am UTC

Re: An old Bob Kraus puzzle from MathPuzzle

Postby Jsty » Tue Apr 13, 2010 12:32 am UTC

Spoiler:
165 different values of N, but how is that 165 solutions? For each N there are 5 possible values of F (and V follows). Counting just the different Ns makes it hard to follow your solution.

I suppose you're right, that's not technically 165 solutions, it's just 165 values of N. My thought process figured that once I knew which N and which function it was, I knew V.

Spoiler:
Can you give an example of a solution that only has one possible function? I don't think I get what you mean.

As I think of it, there are some values of V that can only come from one pair of (N, F) and that the holder knows they can't be N (or F) instead *. The corresponding (N, F) pairs are eliminated here. Other than that, any N can still have any F, no? The holders of N and F can't know each other's number as they are totally independent before the question.

Are there really 64 values of N that are eliminated with all values of F? Intuitively it feels way too much, and a quick, possibly erroneous check tells me there would be no such Ns at all. Even if 64 were actually eliminated, the (N, F) pairs that were eliminated from other Ns can't be ignored either in the rest of the solution. Or are you counting something else than just the possible values of N here?

(*) I assume you're treating the problem like the students don't necessarily know if they have N or V at the start, because you're later using "the person with a N can't decide if it's a N or a V".


What I meant by a solution with only one possible function is an N that, when run through the F(N) gambit, has a V which is also found in the solution set N. For instance, N=117, F1(N)=9, F2(N)=7, F3(N)=51, F4(N)=345, F5(N)=1. Only F4(N) results in a V which could also be an N. Unfortunately though, F4(V) has no results which fall in the current N or V solution sets. Btw, I assumed that the 5th function was erroneous from the start, since I couldn't figure out how to script it in excel.

Once the teacher first asked whether anyone had a solution, it became obvious that the students don't necessarily know if they have N or V at the start. You're right, the corresponding (N, F) pairs are eliminated. At that point though, any N can only have a F with a valid V. Since you also know that your V looks like an N, you also need to eliminate any V's which, if they were actually an N, would have been eliminated. Also, as far as valid F's go, you can start reducing the possibilities here too, because not all functions will create a valid V using an N.


This was a challenging logic puzzle because I kept thinking I either had the same thought before and had already done it, or that the thought I had was somehow different and I needed to repeat the step I'd already done again.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 13 guests