wu :: forums
wu :: forums - Guess the coins

Welcome, Guest. Please Login or Register.
Nov 21st, 2018, 10:27am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: SMQ, Icarus, Eigenray, Grimbal, towr, william wu, ThudnBlunder)
   Guess the coins
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Guess the coins  (Read 822 times)
Altamira_64
Junior Member
**





   


Posts: 116
Guess the coins  
« on: Apr 8th, 2016, 10:23am »
Quote Quote Modify 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: male
Posts: 880
Re: Guess the coins  
« Reply #1 on: Apr 8th, 2016, 8:07pm »
Quote Quote Modify 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: male
Posts: 919
Re: Guess the coins  
« Reply #2 on: Apr 10th, 2016, 3:57am »
Quote Quote Modify 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 10th, 2016, 4:03am by Hippo » IP Logged
Altamira_64
Junior Member
**





   


Posts: 116
Re: Guess the coins  
« Reply #3 on: Apr 11th, 2016, 5:13am »
Quote Quote Modify 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 Smiley
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: Guess the coins  
« Reply #4 on: Apr 14th, 2016, 8:22am »
Quote Quote Modify 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 28th, 2017, 8:18pm »
Quote Quote Modify Modify

This is resurrecting an old thread, but I thought this generalization was really cool and wanted to share my solution.
 
on Apr 14th, 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 <= 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
IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: Guess the coins  
« Reply #6 on: Mar 29th, 2017, 2:04pm »
Quote Quote Modify Modify

on Mar 28th, 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 <= 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.
IP Logged
dudiobugtron
Uberpuzzler
*****





   


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

on Mar 29th, 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 + 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.
IP Logged
impartial_james
Newbie
*





   


Posts: 3
Re: Guess the coins  
« Reply #8 on: Mar 30th, 2017, 3:22pm »
Quote Quote Modify 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)(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
00011110000111100001111000011110000111100001111000 0111100001111000
00000010011011111111110110010000000000100110111111 1111011001000000
000000000000000000100100100100100110110110110110111111111111111111
 
 
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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