Author 
Topic: Guess the coins (Read 918 times) 

Altamira_64
Junior Member
Posts: 116


Guess the coins
« on: Apr 8^{th}, 2016, 10:23am » 
Quote Modify

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?


IP Logged 



pex
Uberpuzzler
Gender:
Posts: 880


Re: Guess the coins
« Reply #1 on: Apr 8^{th}, 2016, 8:07pm » 
Quote Modify

Yes. hidden:  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 


IP Logged 



Hippo
Uberpuzzler
Gender:
Posts: 919


Re: Guess the coins
« Reply #2 on: Apr 10^{th}, 2016, 3:57am » 
Quote Modify

I got 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. BTW: Both this challenge and 8 apples seems to me should be classified as medium. (Once you know the answer ... there is no doubt ...)

« Last Edit: Apr 10^{th}, 2016, 4:03am by Hippo » 
IP Logged 



Altamira_64
Junior Member
Posts: 116


Re: Guess the coins
« Reply #3 on: Apr 11^{th}, 2016, 5:13am » 
Quote Modify

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


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2826


Re: Guess the coins
« Reply #4 on: Apr 14^{th}, 2016, 8:22am » 
Quote Modify

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?


IP Logged 



impartial_james
Newbie
Posts: 3


Re: Guess the coins
« Reply #5 on: Mar 28^{th}, 2017, 8:18pm » 
Quote Modify

This is resurrecting an old thread, but I thought this generalization was really cool and wanted to share my solution. on Apr 14^{th}, 2016, 8:22am, 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 <= 3^{k} + 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 3^{k}+1 0's, followed by (3^{k}1)/2 of the pair 10, followed by 3^{k}+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 3^{k} 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


IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2826


Re: Guess the coins
« Reply #6 on: Mar 29^{th}, 2017, 2:04pm » 
Quote Modify

on Mar 28^{th}, 2017, 8:18pm, 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 <= 3^{k} + 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} + n1 For each subset, you have [0,n] hits, giving you (n+1)^{k} possible ordered ktuples of answers. the first of the n consecutive coins can't be in the last (n1) coins, so there are C  (n1) possible sets of n consecutive coins  so if that's more than the number of possible answers, then there must be some indistinguishable cases.


IP Logged 



dudiobugtron
Uberpuzzler
Posts: 735


Re: Guess the coins
« Reply #7 on: Mar 30^{th}, 2017, 11:28am » 
Quote Modify

on Mar 29^{th}, 2017, 2:04pm, 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} + n1 For each subset, you have [0,n] hits, giving you (n+1)^{k} possible ordered ktuples of answers. the first of the n consecutive coins can't be in the last (n1) coins, so there are C  (n1) 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} + n1 = 3^{k} + 1 when n = 2.


IP Logged 



impartial_james
Newbie
Posts: 3


Re: Guess the coins
« Reply #8 on: Mar 30^{th}, 2017, 3:22pm » 
Quote Modify

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)(n1)  n(n1) = (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 (0^{n})^{m} + (0^{n1}1^{1})^{m} +(0^{n2}1^{2})^{m} + ... + (0^{1}1^{n1})^{m} + (1^{n})^{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 00011110000111100001111000011110000111100001111000 0111100001111000 00000010011011111111110110010000000000100110111111 1111011001000000 000000000000000000100100100100100110110110110110111111111111111111


IP Logged 



