wu :: forums « wu :: forums - Guess the coins » Welcome, Guest. Please Login or Register. Jan 17th, 2022, 12:09pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: towr, Eigenray, william wu, Grimbal, SMQ, ThudnBlunder, Icarus)    Guess the coins « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Guess the coins  (Read 1208 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: 2844
 Re: Guess the coins   « Reply #4 on: Apr 14th, 2016, 8:22am » Quote Modify

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: 2844
 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »