wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Guess the coins
        
(Message started by: Altamira_64 on Apr 8th, 2016, 10:23am)
Title: Guess the coins
Post by Altamira_64 on Apr 8th, 2016, 10:23am
Let's play the following game: You and me have 10 coins in a row in front of us and you secretly select two consecutive coins. I then define two subsets of the 10 coins which I present to you. You must then tell me how many of the coins that you chose belong in each of the two subsets (for example, 2 coins in the 1st subset and none in the 2nd). Then I must guess, only by one attempt, the two coins that you selected. Is there a strategy I can follow so as to always win?
Title: Re: Guess the coins
Post by pex on Apr 8th, 2016, 8:07pm
Yes.

[hideb]The key realization is that if it works, it only just works, since there are 9 possible choices and 9 possible sets of answers to the questions. From here, I just started trying different subsets until everything checked out, which happened pretty quickly, so I didn't feel the need to do any more formal analysis. Number the coins from 0 to 9. One pair of subsets that can be used is {0,1,2,3,5} and {0,1,5,6,7}:

Choice   In first subset   In second subset
  0,1   ........   2   ....................   2
  1,2   ........   2   ....................   1
  2,3   ........   2   ....................   0
  3,4   ........   1   ....................   0
  4,5   ........   1   ....................   1
  5,6   ........   1   ....................   2
  6,7   ........   0   ....................   2
  7,8   ........   0   ....................   1
  8,9   ........   0   ....................   0
[/hideb]
Title: Re: Guess the coins
Post by Hippo on Apr 10th, 2016, 3:57am
I got
[hide]
01456,01678
And the method was simmillar as pex's;).
... The split must contain one border coin and two intervals of lengths 2,3(correct was total length 5) to give 3 answers of each kind ... I made table of answers for each such split (OK not all were needed) and I was looking for "perpendicular" splits.
[/hide]

BTW: Both this challenge and 8 apples seems to me should be classified as medium. (Once you know the answer ... there is no doubt ...)
Title: Re: Guess the coins
Post by Altamira_64 on Apr 11th, 2016, 5:13am
Congrats to both of you.
I agree for the classification of this one, but not for the apples!! The apples took me half a day just to understand the solution, not to mention to think it myself :)
Title: Re: Guess the coins
Post by rmsgrey on Apr 14th, 2016, 8:22am
Follow up question:

If I pick n consecutive coins, and allow you to specify k subsets for me to tell you how many of my coins are in each, how long can the row of coins be for you to always be able to identify my coins?
Title: Re: Guess the coins
Post by impartial_james on Mar 28th, 2017, 8:18pm
This is resurrecting an old thread, but I thought this generalization was really cool and wanted to share my solution.


on 04/14/16 at 08:22:40, rmsgrey wrote:
Follow up question:

If I pick n consecutive coins, and allow you to specify k subsets for me to tell you how many of my coins are in each, how long can the row of coins be for you to always be able to identify my coins?


An obvious upper bound is n <= 3k + 1. This is always achievable. Given the solution for k, I'll show how to construct the solution for k+1.

Thinking of subsets as binary strings of length n, a solution with k questions is a list of k strings. To get the k+1 solution, replace each string s with the string

s + reverse(s) + s

Here, + denotes "concatenation with overlap," where for example 0011 + 1100= 0011100. This produces k of the subsets. The last one is simply 3k+1 0's, followed by (3k-1)/2 of the pair 10, followed by 3k+1 1's.

The process is illustrated below, starting with the k=1 base case. It's not too hard to prove why this works. Essentially, if we replace each binary substring with a ternary substring whose ith number is the number of 1's among the bits i and i+1, then the columns will consist of all 3k possible ternary strings exactly once. This property is preserved when we construct the k+1 solution since we repeat the old columns, then add the row 00...011...122...2 to the end.

k=1:
0011

k=2:
0011100011
0000101111

k=3:
0011100011100011100011100011
0000101111111010000000010111
0000000000101010101111111111
Title: Re: Guess the coins
Post by rmsgrey on Mar 29th, 2017, 2:04pm

on 03/28/17 at 20:18:40, impartial_james wrote:
This is resurrecting an old thread, but I thought this generalization was really cool and wanted to share my solution.


An obvious upper bound is n <= 3k + 1.
[...]


That doesn't address the question asked, which is the maximum value of the total number of coins, call it C.

So, for example, when n=k=2, C=10.

There's an obvious upper bound of C <= (n+1)k + n-1
For each subset, you have [0,n] hits, giving you (n+1)k possible ordered k-tuples of answers. the first of the n consecutive coins can't be in the last (n-1) coins, so there are C - (n-1) possible sets of n consecutive coins - so if that's more than the number of possible answers, then there must be some indistinguishable cases.
Title: Re: Guess the coins
Post by dudiobugtron on Mar 30th, 2017, 11:28am

on 03/29/17 at 14:04:17, rmsgrey wrote:
That doesn't address the question asked, which is the maximum value of the total number of coins, call it C.

So, for example, when n=k=2, C=10.

There's an obvious upper bound of C <= (n+1)k + n-1
For each subset, you have [0,n] hits, giving you (n+1)k possible ordered k-tuples of answers. the first of the n consecutive coins can't be in the last (n-1) coins, so there are C - (n-1) possible sets of n consecutive coins - so if that's more than the number of possible answers, then there must be some indistinguishable cases.


I think impartial_james was just solving the n=2 case, and was using n to represent what you are calling C.

(n+1)k + n-1 = 3k + 1 when n = 2.
Title: Re: Guess the coins
Post by impartial_james on Mar 30th, 2017, 3:22pm
Whoops, I did misunderstand the question. I've solved the problem for n=2. For general n, the obvious upper bound of (n+1)^k + n - 1 is still attainable.

Supposing we have a solution for (n,k), here's how to get the solution for (n,k+1). Let s' denote the reverse of s, and let s1 + s2 denote "concatenation with overlap," where n - 1 bits are overlapped. Replace each string s in the (n,k) solution with

s + s' + s + s' + ...    [n+1 summands total]

Each summand has length (n+1)^k + n - 1, so subtracting the overlaps, the length of the result is (n+1)^(k+1) + (n+1)(n-1) - n(n-1) = (n+1)^(k+1) + n - 1, i.e. is the correct length.

We've constructed k strings so far and need one more. Noting that (n+1)^k + n - 1 is a multiple of n, let m = ((n+1)^k + n - 1)/n. The final string is

(0n)m + (0n-111)m +(0n-212)m + ...  + (011n-1)m + (1n)m    [n+1 summands total]

Here, exponentiation is repeated concatenation, (011)3 = 011011011, while + is overlapping concatenation.

Some examples:

n=3, k=1:
000111

n=3, k=2:
000111100001111000
000000100110111111

n=3, k=3
000111100001111000011110000111100001111000011110000111100001111000
000000100110111111111101100100000000001001101111111111011001000000
000000000000000000100100100100100110110110110110111111111111111111


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board