Card game rigging
up vote
8
down vote
favorite
You and your friend are playing a game with a deck of cards numbered 1 to N.
You will first put the deck of cards in whatever order you want. Next your friend will choose an option: "A" or "B". Finally, you will give your friend each card of the deck in order. For each card, your friend may either choose to keep it or discard it.
If they chose "A", your friend can only keep a card if it has a smaller number than the last card they kept. If they chose "B", they can only keep a card if it has a greater number than the last card they kept.
You know your friend is a cheater, and they know the order of the cards beforehand. How should you order the cards so your friend keeps the least # of cards possible?
Example:
There are 3 cards. Then you should order them 3, 1, 2. There is no option with better answer.
Source: COCI '14 Contest 6 #4 Kratki
Hint:
The answer for 9 cards is 3
strategy
New contributor
add a comment |
up vote
8
down vote
favorite
You and your friend are playing a game with a deck of cards numbered 1 to N.
You will first put the deck of cards in whatever order you want. Next your friend will choose an option: "A" or "B". Finally, you will give your friend each card of the deck in order. For each card, your friend may either choose to keep it or discard it.
If they chose "A", your friend can only keep a card if it has a smaller number than the last card they kept. If they chose "B", they can only keep a card if it has a greater number than the last card they kept.
You know your friend is a cheater, and they know the order of the cards beforehand. How should you order the cards so your friend keeps the least # of cards possible?
Example:
There are 3 cards. Then you should order them 3, 1, 2. There is no option with better answer.
Source: COCI '14 Contest 6 #4 Kratki
Hint:
The answer for 9 cards is 3
strategy
New contributor
I was about to type an answer, but then I realized I had missed a rule aout discarding.
– Weckar E.
5 hours ago
add a comment |
up vote
8
down vote
favorite
up vote
8
down vote
favorite
You and your friend are playing a game with a deck of cards numbered 1 to N.
You will first put the deck of cards in whatever order you want. Next your friend will choose an option: "A" or "B". Finally, you will give your friend each card of the deck in order. For each card, your friend may either choose to keep it or discard it.
If they chose "A", your friend can only keep a card if it has a smaller number than the last card they kept. If they chose "B", they can only keep a card if it has a greater number than the last card they kept.
You know your friend is a cheater, and they know the order of the cards beforehand. How should you order the cards so your friend keeps the least # of cards possible?
Example:
There are 3 cards. Then you should order them 3, 1, 2. There is no option with better answer.
Source: COCI '14 Contest 6 #4 Kratki
Hint:
The answer for 9 cards is 3
strategy
New contributor
You and your friend are playing a game with a deck of cards numbered 1 to N.
You will first put the deck of cards in whatever order you want. Next your friend will choose an option: "A" or "B". Finally, you will give your friend each card of the deck in order. For each card, your friend may either choose to keep it or discard it.
If they chose "A", your friend can only keep a card if it has a smaller number than the last card they kept. If they chose "B", they can only keep a card if it has a greater number than the last card they kept.
You know your friend is a cheater, and they know the order of the cards beforehand. How should you order the cards so your friend keeps the least # of cards possible?
Example:
There are 3 cards. Then you should order them 3, 1, 2. There is no option with better answer.
Source: COCI '14 Contest 6 #4 Kratki
Hint:
The answer for 9 cards is 3
strategy
strategy
New contributor
New contributor
edited 11 hours ago
New contributor
asked 12 hours ago
sunny-lan
1875
1875
New contributor
New contributor
I was about to type an answer, but then I realized I had missed a rule aout discarding.
– Weckar E.
5 hours ago
add a comment |
I was about to type an answer, but then I realized I had missed a rule aout discarding.
– Weckar E.
5 hours ago
I was about to type an answer, but then I realized I had missed a rule aout discarding.
– Weckar E.
5 hours ago
I was about to type an answer, but then I realized I had missed a rule aout discarding.
– Weckar E.
5 hours ago
add a comment |
3 Answers
3
active
oldest
votes
up vote
10
down vote
accepted
I think you can get the bound down to
$lceil sqrt{N} rceil$, that is the square root of $N$, rounded up.
In the following way
Order the cards from $1$ to $N$ and partition them into $left[ frac{N}{lceil sqrt{N} rceil} right]$ subsets of size $lceil sqrt{N} rceil$ plus one additional subset of the leftovers (may have size zero). Then, reverse the order of the cards within each subset.
For example for $N=18$, we divide the cards into $3$ subsets of size $5$ and one of size $3$, i.e, $$ 1,2,3,4,5|6,7,8,9,10|11,12,13,14,15|16,17,18$$ then reverse the cards within each subset $$5,4,3,2,1|10,9,8,7,6|15,14,13,12,11|18,17,16$$ Then our maximum increasing or decreasing subsequence has size $5$.
For $N=9$ the corresponding ordering is $3,2,1,6,5,4,9,8,7$ which indeed has its longest increasing or decreasing subsequence with size $3$.
Why this works
To obtain an decreasing subsequence (option A) your friend must choose all of their cards to be within one of the partitions above (as cards between partitions are in increasing order). This gives them a maximum of $lceil sqrt{N} rceil$. On the other hand, if they choose option B, then all the cards they pick must be in different partitions as defined above, which gives them a maximum of $left[ frac{N}{lceil sqrt{N} rceil} right] leq frac{N}{lceil sqrt{N} rceil} leq lceil sqrt{N} rceil$. I think this is the best we can do while balancing the advantages of the two options.
That is the right answer, but I think you might be able to offer a stronger proof
– sunny-lan
10 hours ago
Thanks, do you mean proving that this is a lower bound?
– hexomino
10 hours ago
yeah, instead of saying its balanced
– sunny-lan
5 hours ago
add a comment |
up vote
3
down vote
There is actually a theorem which basically says that hexomino's solution is optimal. The name is
Erdős–Szekeres theorem.
New contributor
add a comment |
up vote
2
down vote
Maybe I'm missing something, but
Put the cards 1..N/2 in increasing order, and N..N/2+1 in decreasing order. The friend gets at most N/2 cards (rounded down).
For example, with N=9:
1, 2, 3, 4, 9, 8, 7, 6, 5
The friend gets either 8, 7, 6 and 5 (option A) or 2, 3, 4 and 9 (option B).
With N=8:
1, 2, 3, 4, 8, 7, 6, 5
The friend gets either 7, 6 and 5 (option A) or 2, 3, 4 and 8 (option B).
1
Good answer, but you can do better
– sunny-lan
12 hours ago
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
10
down vote
accepted
I think you can get the bound down to
$lceil sqrt{N} rceil$, that is the square root of $N$, rounded up.
In the following way
Order the cards from $1$ to $N$ and partition them into $left[ frac{N}{lceil sqrt{N} rceil} right]$ subsets of size $lceil sqrt{N} rceil$ plus one additional subset of the leftovers (may have size zero). Then, reverse the order of the cards within each subset.
For example for $N=18$, we divide the cards into $3$ subsets of size $5$ and one of size $3$, i.e, $$ 1,2,3,4,5|6,7,8,9,10|11,12,13,14,15|16,17,18$$ then reverse the cards within each subset $$5,4,3,2,1|10,9,8,7,6|15,14,13,12,11|18,17,16$$ Then our maximum increasing or decreasing subsequence has size $5$.
For $N=9$ the corresponding ordering is $3,2,1,6,5,4,9,8,7$ which indeed has its longest increasing or decreasing subsequence with size $3$.
Why this works
To obtain an decreasing subsequence (option A) your friend must choose all of their cards to be within one of the partitions above (as cards between partitions are in increasing order). This gives them a maximum of $lceil sqrt{N} rceil$. On the other hand, if they choose option B, then all the cards they pick must be in different partitions as defined above, which gives them a maximum of $left[ frac{N}{lceil sqrt{N} rceil} right] leq frac{N}{lceil sqrt{N} rceil} leq lceil sqrt{N} rceil$. I think this is the best we can do while balancing the advantages of the two options.
That is the right answer, but I think you might be able to offer a stronger proof
– sunny-lan
10 hours ago
Thanks, do you mean proving that this is a lower bound?
– hexomino
10 hours ago
yeah, instead of saying its balanced
– sunny-lan
5 hours ago
add a comment |
up vote
10
down vote
accepted
I think you can get the bound down to
$lceil sqrt{N} rceil$, that is the square root of $N$, rounded up.
In the following way
Order the cards from $1$ to $N$ and partition them into $left[ frac{N}{lceil sqrt{N} rceil} right]$ subsets of size $lceil sqrt{N} rceil$ plus one additional subset of the leftovers (may have size zero). Then, reverse the order of the cards within each subset.
For example for $N=18$, we divide the cards into $3$ subsets of size $5$ and one of size $3$, i.e, $$ 1,2,3,4,5|6,7,8,9,10|11,12,13,14,15|16,17,18$$ then reverse the cards within each subset $$5,4,3,2,1|10,9,8,7,6|15,14,13,12,11|18,17,16$$ Then our maximum increasing or decreasing subsequence has size $5$.
For $N=9$ the corresponding ordering is $3,2,1,6,5,4,9,8,7$ which indeed has its longest increasing or decreasing subsequence with size $3$.
Why this works
To obtain an decreasing subsequence (option A) your friend must choose all of their cards to be within one of the partitions above (as cards between partitions are in increasing order). This gives them a maximum of $lceil sqrt{N} rceil$. On the other hand, if they choose option B, then all the cards they pick must be in different partitions as defined above, which gives them a maximum of $left[ frac{N}{lceil sqrt{N} rceil} right] leq frac{N}{lceil sqrt{N} rceil} leq lceil sqrt{N} rceil$. I think this is the best we can do while balancing the advantages of the two options.
That is the right answer, but I think you might be able to offer a stronger proof
– sunny-lan
10 hours ago
Thanks, do you mean proving that this is a lower bound?
– hexomino
10 hours ago
yeah, instead of saying its balanced
– sunny-lan
5 hours ago
add a comment |
up vote
10
down vote
accepted
up vote
10
down vote
accepted
I think you can get the bound down to
$lceil sqrt{N} rceil$, that is the square root of $N$, rounded up.
In the following way
Order the cards from $1$ to $N$ and partition them into $left[ frac{N}{lceil sqrt{N} rceil} right]$ subsets of size $lceil sqrt{N} rceil$ plus one additional subset of the leftovers (may have size zero). Then, reverse the order of the cards within each subset.
For example for $N=18$, we divide the cards into $3$ subsets of size $5$ and one of size $3$, i.e, $$ 1,2,3,4,5|6,7,8,9,10|11,12,13,14,15|16,17,18$$ then reverse the cards within each subset $$5,4,3,2,1|10,9,8,7,6|15,14,13,12,11|18,17,16$$ Then our maximum increasing or decreasing subsequence has size $5$.
For $N=9$ the corresponding ordering is $3,2,1,6,5,4,9,8,7$ which indeed has its longest increasing or decreasing subsequence with size $3$.
Why this works
To obtain an decreasing subsequence (option A) your friend must choose all of their cards to be within one of the partitions above (as cards between partitions are in increasing order). This gives them a maximum of $lceil sqrt{N} rceil$. On the other hand, if they choose option B, then all the cards they pick must be in different partitions as defined above, which gives them a maximum of $left[ frac{N}{lceil sqrt{N} rceil} right] leq frac{N}{lceil sqrt{N} rceil} leq lceil sqrt{N} rceil$. I think this is the best we can do while balancing the advantages of the two options.
I think you can get the bound down to
$lceil sqrt{N} rceil$, that is the square root of $N$, rounded up.
In the following way
Order the cards from $1$ to $N$ and partition them into $left[ frac{N}{lceil sqrt{N} rceil} right]$ subsets of size $lceil sqrt{N} rceil$ plus one additional subset of the leftovers (may have size zero). Then, reverse the order of the cards within each subset.
For example for $N=18$, we divide the cards into $3$ subsets of size $5$ and one of size $3$, i.e, $$ 1,2,3,4,5|6,7,8,9,10|11,12,13,14,15|16,17,18$$ then reverse the cards within each subset $$5,4,3,2,1|10,9,8,7,6|15,14,13,12,11|18,17,16$$ Then our maximum increasing or decreasing subsequence has size $5$.
For $N=9$ the corresponding ordering is $3,2,1,6,5,4,9,8,7$ which indeed has its longest increasing or decreasing subsequence with size $3$.
Why this works
To obtain an decreasing subsequence (option A) your friend must choose all of their cards to be within one of the partitions above (as cards between partitions are in increasing order). This gives them a maximum of $lceil sqrt{N} rceil$. On the other hand, if they choose option B, then all the cards they pick must be in different partitions as defined above, which gives them a maximum of $left[ frac{N}{lceil sqrt{N} rceil} right] leq frac{N}{lceil sqrt{N} rceil} leq lceil sqrt{N} rceil$. I think this is the best we can do while balancing the advantages of the two options.
edited 10 hours ago
answered 11 hours ago
hexomino
33.7k297159
33.7k297159
That is the right answer, but I think you might be able to offer a stronger proof
– sunny-lan
10 hours ago
Thanks, do you mean proving that this is a lower bound?
– hexomino
10 hours ago
yeah, instead of saying its balanced
– sunny-lan
5 hours ago
add a comment |
That is the right answer, but I think you might be able to offer a stronger proof
– sunny-lan
10 hours ago
Thanks, do you mean proving that this is a lower bound?
– hexomino
10 hours ago
yeah, instead of saying its balanced
– sunny-lan
5 hours ago
That is the right answer, but I think you might be able to offer a stronger proof
– sunny-lan
10 hours ago
That is the right answer, but I think you might be able to offer a stronger proof
– sunny-lan
10 hours ago
Thanks, do you mean proving that this is a lower bound?
– hexomino
10 hours ago
Thanks, do you mean proving that this is a lower bound?
– hexomino
10 hours ago
yeah, instead of saying its balanced
– sunny-lan
5 hours ago
yeah, instead of saying its balanced
– sunny-lan
5 hours ago
add a comment |
up vote
3
down vote
There is actually a theorem which basically says that hexomino's solution is optimal. The name is
Erdős–Szekeres theorem.
New contributor
add a comment |
up vote
3
down vote
There is actually a theorem which basically says that hexomino's solution is optimal. The name is
Erdős–Szekeres theorem.
New contributor
add a comment |
up vote
3
down vote
up vote
3
down vote
There is actually a theorem which basically says that hexomino's solution is optimal. The name is
Erdős–Szekeres theorem.
New contributor
There is actually a theorem which basically says that hexomino's solution is optimal. The name is
Erdős–Szekeres theorem.
New contributor
New contributor
answered 55 mins ago
Viki
311
311
New contributor
New contributor
add a comment |
add a comment |
up vote
2
down vote
Maybe I'm missing something, but
Put the cards 1..N/2 in increasing order, and N..N/2+1 in decreasing order. The friend gets at most N/2 cards (rounded down).
For example, with N=9:
1, 2, 3, 4, 9, 8, 7, 6, 5
The friend gets either 8, 7, 6 and 5 (option A) or 2, 3, 4 and 9 (option B).
With N=8:
1, 2, 3, 4, 8, 7, 6, 5
The friend gets either 7, 6 and 5 (option A) or 2, 3, 4 and 8 (option B).
1
Good answer, but you can do better
– sunny-lan
12 hours ago
add a comment |
up vote
2
down vote
Maybe I'm missing something, but
Put the cards 1..N/2 in increasing order, and N..N/2+1 in decreasing order. The friend gets at most N/2 cards (rounded down).
For example, with N=9:
1, 2, 3, 4, 9, 8, 7, 6, 5
The friend gets either 8, 7, 6 and 5 (option A) or 2, 3, 4 and 9 (option B).
With N=8:
1, 2, 3, 4, 8, 7, 6, 5
The friend gets either 7, 6 and 5 (option A) or 2, 3, 4 and 8 (option B).
1
Good answer, but you can do better
– sunny-lan
12 hours ago
add a comment |
up vote
2
down vote
up vote
2
down vote
Maybe I'm missing something, but
Put the cards 1..N/2 in increasing order, and N..N/2+1 in decreasing order. The friend gets at most N/2 cards (rounded down).
For example, with N=9:
1, 2, 3, 4, 9, 8, 7, 6, 5
The friend gets either 8, 7, 6 and 5 (option A) or 2, 3, 4 and 9 (option B).
With N=8:
1, 2, 3, 4, 8, 7, 6, 5
The friend gets either 7, 6 and 5 (option A) or 2, 3, 4 and 8 (option B).
Maybe I'm missing something, but
Put the cards 1..N/2 in increasing order, and N..N/2+1 in decreasing order. The friend gets at most N/2 cards (rounded down).
For example, with N=9:
1, 2, 3, 4, 9, 8, 7, 6, 5
The friend gets either 8, 7, 6 and 5 (option A) or 2, 3, 4 and 9 (option B).
With N=8:
1, 2, 3, 4, 8, 7, 6, 5
The friend gets either 7, 6 and 5 (option A) or 2, 3, 4 and 8 (option B).
answered 12 hours ago
jafe
13.9k35143
13.9k35143
1
Good answer, but you can do better
– sunny-lan
12 hours ago
add a comment |
1
Good answer, but you can do better
– sunny-lan
12 hours ago
1
1
Good answer, but you can do better
– sunny-lan
12 hours ago
Good answer, but you can do better
– sunny-lan
12 hours ago
add a comment |
sunny-lan is a new contributor. Be nice, and check out our Code of Conduct.
sunny-lan is a new contributor. Be nice, and check out our Code of Conduct.
sunny-lan is a new contributor. Be nice, and check out our Code of Conduct.
sunny-lan is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f75756%2fcard-game-rigging%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
I was about to type an answer, but then I realized I had missed a rule aout discarding.
– Weckar E.
5 hours ago