2
$\begingroup$

You are trapped in a room. In front of you, there is a table on which there is an infinite number of stacks of cards each containing an infinite number of black or white cards.

Two stacks are considered to be "similar" if when you put the stacks side by side, every $p$-th pair of adjacent cards has the same color (for some prime number $p$).

You have a infinite number of empty tables, each labeled with a positive integer. To be able to leave the room, you must move stacks onto the other tables such that no table contains two similar stacks.

You look at the stacks, and see that for any stack, it would be possible to move all stacks that are similar to it onto the other tables. However, you're not sure how to move all stacks such that there's no two similar stacks on the same table.

Is it possible to achieve this? If yes, how?

Notes: A table can contain uncountably many stacks. You are able to move uncountable many stacks. You can use the axiom of choice. I'll be adding one hint every two days.

$\endgroup$
  • $\begingroup$ I think I'm missing something here. If the table has an uncountable number of all-white stacks, any pair of stacks are similar, so any way to partition them among countably many tables will leave a table with similar stacks. $\endgroup$ – xnor Dec 9 '18 at 8:39
  • $\begingroup$ You're right, I forgot a detail: all the stacks are different from each other. $\endgroup$ – Stefan Dec 9 '18 at 8:41
  • $\begingroup$ It still seems to me like you can get the same issue. Say all the stacks have every even card white, and the odd cards are all different black/white sequences. Then, they are still all similar. $\endgroup$ – xnor Dec 9 '18 at 8:42
  • $\begingroup$ @xnor: Fixed it, it should have the intended solution now. $\endgroup$ – Stefan Dec 9 '18 at 9:08
  • 2
    $\begingroup$ Can the problem be stated then as "show that every graph with countable degree for each vertex has countable chromatic number"? $\endgroup$ – xnor Dec 9 '18 at 10:48
3
$\begingroup$

Okay, alternate approach:

Maybe @xnor already solved the puzzle in the comments: "every graph with countable degree for each vertex has countable chromatic number" (because every connected component is countable)

I am labelling the start table (where all the stacks are initially) with 0, and the rest of the tables with positive integers. I assume:

- An ordinal number is assigned to each stack (requires the axiom of choice)
- At any time, for any ordinal, I know on which table that stack is
- For any ordinal $\alpha$, and every positive integer $n$, I can compute the ordinal number of a stack which is similar to $\alpha$, and that these cover all the stacks similar to $\alpha$. (may or may not require axiom of choice, I guess it depends how you interpret the question?)
- I can perform uncountable well-founded supertasks, and the position of stacks remains well-defined at limit ordinals (requires the law of excluded middle, which can be considered a consequence of the axiom of choice, if you like)

The rest is constructive (no further appeals to axiom of choice / law of excluded middle):

1. For every ordinal number $\alpha$:
2. Find the stack labelled $\alpha$. If it's not on table 0, skip to 10.
3. Move it from table 0 to table 1.
4. For every positive integer $n$:
5. Look at the stack $\beta$ you just put there, if any (you can compute $\beta$ from $(\alpha,n)$ if you forgot).
6. For every positive integer $m$:
7. Find the $m^{th}$ stack similar to $\beta$. If it is not on table 0, leave it. Otherwise, move it from table 0 to table $2^m n - 2^{m-1} + 1$. (Or use your favourite bijection from sequences of positive integers to positive integers.)
8. Repeat 7 for all $m$.
9. Repeat 5-8 for all $n$. (At the end of this countable well-founded supertask, none of the stacks remaining on table 0 are similar to any of the stacks on the other tables.)
10. Repeat 2-9 for all $\alpha$. (uncountable well-founded supertask)

[EDIT: explanation added later]

For step 7, why you can be sure there isn't a stack similar to the one you're moving the stack already on the table you're moving it to:
Because I am using a bijection bewteen sequences of positive integers and positive integers. The result is that, I am moving the stack from table 0, and am placing it onto a table onto which I haven't placed any stack yet this round. And for previous rounds, at the end of step 9, we know none of the stacks on table 0 are similar to any of the stacks on the other tables.

$\endgroup$
  • $\begingroup$ I'm not sure I understand step 7. Could you explain why you can be sure that the table you're moving the stack to doesn't already have a similar stack on it (from a different repetition of loop 1)? $\endgroup$ – Stefan Dec 10 '18 at 23:48
  • $\begingroup$ @Stefan - ok, edited to add explanation! $\endgroup$ – deep thought Dec 11 '18 at 0:00
  • $\begingroup$ If I'm understanding correctly, you've moved the stacks similar to stack α, the stacks similar to stacks similar to α, but there may be stacks similar to stacks similar to a stacks similar to α left on table 0... Am I missing something? $\endgroup$ – Stefan Dec 11 '18 at 0:16
  • $\begingroup$ @Stefan - Example: alpha went on table 1, if it wasn't already placed. The 1st stack similar to alpha went on table 2, when n=1 and m=1, if it wasn't already placed. The 1st stack similar to the 1st stack similar to alpha went on table 4, when n=2 and m=1, if it wasn't already placed. The 1st stack similar to the 1st stack similar to the 1st stack similar to alpha went on table 8, when n=4 and m=1, if it wasn't already placed. The 1st stack similar to 1st stack similar to the 1st stack similar to the 1st stack similar to alpha went on table 16, when n=8 and m=1, if it wasn't already placed... $\endgroup$ – deep thought Dec 11 '18 at 0:26
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Transitive_closure ... yes, after capturing all the finite sequences, we are done! $\endgroup$ – deep thought Dec 11 '18 at 0:43
0
$\begingroup$

So far I can only come up with an algorithm that will take a countably infinite number of steps to complete, as follows.

First label the starting table as table -1, you will only be taking cards off this table. Label the rest of the (as yet unused) countable number of tables with the positive integers 0,1,2...

Now, find the stacks with all white cards and all black cards (if they exist) and place them on table 0.

Now identify the subset of stacks (remaining on table -1) with every second card white or every second card black. You know (from paragraph 4) that you can choose one of them and place it and all similar stacks from this subset on different tables. Do so, starting at table 1. Then for each table i, move its contents to table 2*i, so tables 2,4,6... may have card stacks on them, but tables 1,3,5... are free.

Now identify all remaining stacks on table -1 with every third card white or every third card black. Place one of them on table 1 and place all the remaining similar stacks from this subset on different odd numbered tables 3,5,7... (as allowed by paragraph 4 again). Then for each table, move its contents to table 2*i, so tables 2,4,6... may have card stacks on them, but tables 1,3,5... are free.

Repeat the above, each time choosing the subset of stacks from table -1 with every nth prime white or every nth prime black.

As the primes are countable, you can complete this procedure after a countably infinite number of steps. If there are any stacks remaining on table -1 then they cannot be similar to each other.

$\endgroup$
  • $\begingroup$ The condition for two stacks to be similar is that every p-th pair of adjacent cards (when putting the stacks side-by-side) has a single color, but not all p-th cards in each stack have necessarily the same color. This would require the algorithm to have uncountable many steps, but you only have countably many tables. $\endgroup$ – Stefan Dec 9 '18 at 23:42
  • $\begingroup$ @Stefan - ok, I take your point. I will think on it a little longer...it may still be possible to rescue the algorithm. $\endgroup$ – Penguino Dec 10 '18 at 2:03
0
$\begingroup$

Notice how

OP says that there could be uncountably many stacks, but is carefully avoiding saying that there are uncountably many.

Now clearly,

an object with zero volume has no colour; but one cannot have an infinitely large object on a table. Nor can I move an infinitely large object for that matter.

Therefore

The sum of the volumes of all the cards, each of which is positive, is finite; thus there are only countably many stacks to begin with. Thus I can put one on each table.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.