Puzzles with numbers and things

[Robert602]

I'll chip in with 9 and 2, although thinking about it I can't see a problem with 8 and 3 either...

Don't think it's 6 and 2 because if it was, Gordon couldn't know that Charlie wouldnt know (as for all Gordon knows, Charlie has the product 15 and therefore would know). If you get me .

[abextra]

Meanwhile, I found another little puzzle:

given two integers m and n (both bigger than 1 and m Charlie: I couldn't tell the numbers yet.
Gordon: I knew that.
Charlie: Now I can.
Gordon: So can I.

(and as usual, we need the proof, that no other pairings are possible )

Maybe m=2 , n=6 ?

[Robert602]

Yeah my efforts were handed in last week. I had a class on it today in which 2n-4 (n>4) was confirmed as the correct answer, but the good doctor gave us another couple of days to think about a proof (for curiosity's sake) before it's revealed to us. He did say the proof was 'the difficult bit'.

1 point to DGE for getting the right result, and I'll offer a bonus point for a proof should anyone manage to come up with one.

[davis_greatest]

Yes, please send them. I think robert has had to give his homework in by now, so he won't be cheating

[snookersfun]

I started to work on my own problem and you definitely need some computer-help. Excel will do, I think.
Also, having read up on Robert's stuff, there (quite amazingly- as one only saves that one call) is no counter example (but there are indirect proofs in that direction (not that I understand them); do you want some references?)

[davis_greatest]

snookersfun, can this be done without a computer (or writing a lot of numbers out by hand)?

And robert602, no, I haven't managed to prove that 2n-4 is the minimum possible in your question (for n>=4). Do you have a proof or counterexample?

[snookersfun]

So, no proof yet?

Meanwhile, I found another little puzzle:

given two integers m and n (both bigger than 1 and m Charlie: I couldn't tell the numbers yet.
Gordon: I knew that.
Charlie: Now I can.
Gordon: So can I.

(and as usual, we need the proof, that no other pairings are possible )

[davis_greatest]

I can do that:
1-2
3-4
2-3
1-4

....
Yes!

[snookersfun]

I can do that:
1-2
3-4
2-3
1-4

[elvaago]

How do you do 4 matches in 4 calls?

[davis_greatest]

Well, yes, the proofs are the hard part, but I don't think one can understand a problem without understanding the proof.

If you've shown that for 4 people you can do it in 4 calls (which is easy), then you can see that each time you add one more person, 2 extra calls will suffice.

Suppose that with n=N (>=4), it can be done in 2N-4 calls.

Then when n=N+1,

get the (N+1)st person to speak to the 1st person : 1 call
get the N people to spread the scores among themselves: 2N-4 calls
get the (N+1)st person to speak to the 1st person again: 1 call

Total 2N-2 = 2(N+1) - 4 calls.

So, by induction, we know that the lower bound is no greater than 2n-4 (for n>=4). Now prove it is no less!

[snookersfun]

well, if you can't, I won't even try.... The proofs are always the hard parts, aren't they.
Just blew my head trying to find the combinations for 5 and 6 (and yes, strangely enough I could).
Somehow it is strange, that one shouldn't need even less phone calls with even higher numbers like 8,16,...

[davis_greatest]

Don't think it matters whether n is odd or even, as long as it's >=4.

I'm trying to see how to show that you can't do it in fewer than 2n-4 calls (it's easy to see that not more than 2n-4 are needed), but can't seem to see an easy way to show this at all...

[snookersfun]

I just got there as well, sorry!!! It is only 4 calls for n=4. Have to think a bit more about the rest (especially uneven numbers)
doing that while trying to feed kids, the washing mashine, giving biology lessons +++
you are not the only one busy
So you earned another point! Congrats

[davis_greatest]

As sure as I can be while trying to type an answer while on the phone to work about something else and typing an email on my other computer about something else entirely Definitely if n>=4, it's easy to find a way to spread the scores with 2n-4 calls.
If n=2 though, you need 1 call, and with n=3 you need 3.