Author |
Topic: Guess the coins (Read 1370 times) |
|
Altamira_64
Junior Member
Posts: 116
|
 |
Guess the coins
« on: Apr 8th, 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 8th, 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 10th, 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 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 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: 2873
|
|
Re: Guess the coins
« Reply #4 on: Apr 14th, 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 28th, 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 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
Gender:
Posts: 2873
|
|
Re: Guess the coins
« Reply #6 on: Mar 29th, 2017, 2:04pm » |
Quote 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: 735
|
|
Re: Guess the coins
« Reply #7 on: Mar 30th, 2017, 11:28am » |
Quote 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 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print