I suppose that one could try something inductive like proving that if you're given a valid partition of $\{1, \ldots, n\}$ then there are always exactly two piles on which you can add $n + 1$ and end up with a valid partition of $\{1, \ldots, n, n +1\}$, but that solution seems to involve some boring case-work. Instead, here's a pretty bijection: I claim that valid partitions are in bijection with partitions of $\{1, \ldots, n\}$ into consecutive strings of integers. I'll denote members of the later set like $123-45-678-9$ to indicate a partition with four parts, one of which contains the two elements 4 and 5. Rather than a proof, here are some examples of the bijection: $123456 \to \{123456, \varnothing, \varnothing\}$ $1-23456 \to \{1, 23456, \varnothing\}$ $12-3456 \to \{12, 3456, \varnothing\}$ $1-2-3456 \to \{1, 2, 3456\}$ $1-23-456 \to \{1456, 23, \varnothing\}$ $1-234-56 \to \{1,234,56\}$ $1-2345-6\to \{16,2345,\varnothing\}$ $1-2-3-456 \to \{1456,2,3\}$ $1-2-34-56 \to \{1,256,34\}$ $1-23-4-56 \to \{14,23,56\}$ $1-23-45-6 \to \{145, 236, \varnothing\}$ Hopefully it's clear from here how to do this in general.

The answer is $3\left(2^n-1\right)$by induction.

Bump.......