Radix Combinatorics, Weights & Digital Properties
Master radix combinatorics: digit-count logarithmic formulas, weight-partitioning theorems (single-pan binary vs. two-pan balanced ternary), base-shift right concatenation, and generalized radix divisibility tests.
1. The Story & Mental Model: Bachet's Weight Puzzle & The Optimal Scale
In 1612, French mathematician Claude-Gaspard Bachet de Méziriac proposed a famous puzzle in his Problèmes Plaisants et Délectables:
"A merchant wants to weigh any integer quantity of grain from to on a balance scale. What is the minimum number of standard weights he must carry in his cart?"
If the merchant places weights on only one pan (opposite the grain), each weight can have only two states: placed on the pan () or left in the cart (). To weigh all consecutive integers from up to , the weights must be the powers of :
To cover up to , he needs weights: (which reach up to ).
But Bachet made a brilliant observation: a balance scale has TWO pans!
You can place a weight on the opposite pan (), omit it (), OR place it on the SAME pan as the grain (, subtracting weight from the other side)!
Because each weight now has THREE distinct states , the optimal weight system is powers of 3 (Balanced Ternary):
With just four weights, the merchant can measure every single integer up to:
For instance, to weigh : place the weight on the right pan, and the weight on the left pan with the grain:
Positional number systems are fundamentally nature's most efficient information-encoding schemes. Understanding how bases encode information unlocks rapid solutions to CAT combinatorics and digital questions.
2. The CAT Question Blueprint: How Radix Combinatorics Appears in the Exam
Look for these recurring question types in CAT:
-
The Weight Set Optimization Problem: The classic single-pan vs. two-pan balance question. Students must immediately connect single-pan to powers of 2 (Binary) and two-pan to powers of 3 (Balanced Ternary).
-
Digit Count of Exponential Numbers: How many digits are needed to express in base 2 or base 36? Solved instantly using .
-
Trailing Zeros in Base : How many trailing zeros does have when written in base 12? Solved by prime-factorizing the base () and applying Legendre's formula.
-
Generalized Divisibility Rules: Testing divisibility of a base- number by (sum of digits) or (alternating sum of digits), perfectly generalizing the decimal rules for 9 and 11.
-
Restricted Digit Combinatorics: Counting how many valid numbers can be formed in base under no-consecutive-identical-digits and parity constraints.
3. Core Concepts, Formulae & Derivations
A. The Exact Digit Count Formula
The number of digits required to represent a positive integer in base :
Equivalence: A number requires exactly digits in base if and only if:
B. The Single-Pan Weight Theorem (Binary System)
Weights available: .
Each weight has coefficient .
-
Total distinct measurable integer weights: to .
-
Minimum weights required to weigh any integer up to :
C. The Two-Pan Weight Theorem (Balanced Ternary System)
Weights available: .
Each weight has coefficient .
-
Total distinct measurable integer weights: to .
-
Minimum weights required to weigh any integer up to :
D. The Digital Right-Shift Multiplier Identity
Appending zeros to the right of a number in base multiplies the number by :
Conversely, the number of trailing zeros of in base equals the largest integer such that .
E. Generalized Radix Divisibility Theorems
For any integer :
-
Divisibility by a divisor of :
Since , . (Only the last digit matters).
-
Divisibility by (The Generalized '9' Rule):
Since , :
is divisible by if and only if the sum of its base- digits is divisible by .
-
Divisibility by (The Generalized '11' Rule):
Since , :
is divisible by if and only if the alternating sum of its base- digits is divisible by .
4. Common Pitfalls & Speed Shortcuts
[!CAUTION]
Single-Pan vs. Two-Pan Balance Confusion:
- When the question specifies weights can be placed on only one side, use powers of 2.
- When the question specifies weights can be placed on either pan, use powers of 3.
Confusing these two models is an instant negative mark in CAT.
[!WARNING]
The Base Factor Trailing Zero Trap:
To find trailing zeros of in base 12, students often test 12 directly. But 12 is composite ().
You must compute the count of prime factor (halved, since ) and prime factor , then take the minimum!
[!TIP]
Digit Count for Powers of the Base:
Any exact power has exactly digits in base (a leading followed by zeros).
For example, has bits (
100000000_2).
Formulas
| Exact Radix Digit Count | |
|---|---|
| Single-Pan Binary Weight Capacity | |
| Two-Pan Balanced Ternary Capacity | |
| Generalized (b - 1) Divisibility | |
| Generalized (b + 1) Divisibility |
Traps and tips
- Pan rules: Single-pan balance uses powers of 2; two-pan balance uses powers of 3 (balanced ternary).
- Trailing zeros of composite radix: Factor base into primes b = p1^e1 * p2^e2, find Legendre counts E_pi(N!), and compute min(floor(E_pi / ei)).
- Divisibility rule alignment: In base 8, sum-of-digits tests divisibility by 7 (8 - 1), NOT 9.
- Exact power digit count: An exact power b^k written in base b always has k + 1 digits (1 followed by k zeros).
Solved examples
Example 2.5.1: Digit Count of Large Exponential Powers across Bases
How many digits are required to express the integer in: (a) base 6, (b) base 36, and (c) binary (base 2)? (Given and ).
Show solution
Part (a): In Base 6
is an exact power of the base .
In base 6, is represented as followed by exactly zeros:
Part (b): In Base 36
Express as a power of :
In base 36, is represented as followed by zeros:
Part (c): In Binary (Base 2)
Apply the logarithmic digit formula:
Convert using change of base:
Substitute the given values:
Multiply by :
Take the floor and add :
Takeaway: For powers of the radix b^k, digit count is simply k + 1; for arbitrary bases, evaluate floor(log b N) + 1.
Example 2.5.2: Bachet's Weight Problem (Single-Pan vs. Two-Pan Balance Scale)
A precious metals merchant must be able to weigh any integer quantity of gold dust from to . Determine: (a) the minimum number of standard weights required if weights can be placed on only one pan (opposing the gold), and (b) the minimum number of weights required if weights may be placed on either pan. Specify the exact weight sets for both systems.
Show solution
Part (a): Single-Pan Balance (Binary Weight System)
Each weight can be either used () or omitted ().
With weights, the maximum measurable weight is the sum of geometric powers of :
Set :
Since and :
Weight set: (total capacity ).
Takeaway: Single-pan balance uses powers of 2 (binary); two-pan balance uses powers of 3 (balanced ternary), cutting required weights nearly in half.
Example 2.5.3: Generalized Radix Divisibility by $(b - 1)$
A four-digit number is written in base 8 as , where is an unknown digit. If this number is known to be exactly divisible by , determine all possible values of the digit .
Show solution
Step 1: Apply the generalized divisibility theorem.
Here the base is , and the divisor is .
Since , we have for all powers .
Therefore, any base-8 number is congruent to the sum of its digits modulo 7:
Step 2: Simplify the congruence.
Reduce modulo 7:
Step 3: Solve for divisibility by 7.
For to be divisible by 7:
Step 4: Filter against allowable base-8 digits.
In base 8, the allowable digits are .
The only digit satisfying in this set is:
Verification:
For , .
Check divisibility: (exact integer!).
Takeaway: In any base b, divisibility by (b - 1) is governed strictly by the sum of digits, exactly like divisibility by 9 in decimal.
Example 2.5.4: Generalized Radix Divisibility by $(b + 1)$ (Alternating Digit Sum)
Without converting to decimal, determine whether the base-6 number is divisible by . If not, find its remainder when divided by .
Show solution
Step 1: Apply the generalized divisibility theorem.
Here the radix is , and the divisor is .
Notice that .
Therefore, powers of the base alternate in sign modulo 7:
Step 2: Compute the alternating sum of digits.
Multiply digits by alternating signs starting with at the units place ():
Step 3: Evaluate modulo 7.
Since the alternating sum is not congruent to , is not divisible by 7.
Its remainder upon division by 7 is .
Verification via Decimal:
Exact confirmation!
Takeaway: In any base b, divisibility by (b + 1) is governed by the alternating sum of digits, directly generalizing the decimal rule for 11.
Example 2.5.5: Trailing Zeros of Factorials in Composite Bases
Determine the exact number of trailing zeros when the decimal factorial is written in duodecimal notation (base 12).
Show solution
Step 1: Understand trailing zeros in a base.
The number of trailing zeros of in base is the highest power such that .
Step 2: Prime factorize the base .
To form one factor of , we require two factors of and one factor of .
Therefore:
where is the exponent of prime in given by Legendre's formula.
Step 3: Compute via Legendre's formula.
E_2(100!) &= \left\lfloor \frac{100}{2} \right\rfloor + \left\lfloor \frac{100}{4} \right\rfloor + \left\lfloor \frac{100}{8} \right\rfloor + \left\lfloor \frac{100}{16} \right\rfloor + \left\lfloor \frac{100}{32} \right\rfloor + \left\lfloor \frac{100}{64} \right\rfloor \\ &= 50 + 25 + 12 + 6 + 3 + 1 = 97 \end{aligned}$$ Number of available pairs of $2$s: $$\left\lfloor \frac{97}{2} \right\rfloor = 48$$ **Step 4: Compute $E_3(100!)$ via Legendre's formula.** $$\begin{aligned} E_3(100!) &= \left\lfloor \frac{100}{3} \right\rfloor + \left\lfloor \frac{100}{9} \right\rfloor + \left\lfloor \frac{100}{27} \right\rfloor + \left\lfloor \frac{100}{81} \right\rfloor \\ &= 33 + 11 + 3 + 1 = 48 \end{aligned}$$ **Step 5: Take the limiting prime factor.** $$k = \min(48, 48) = \mathbf{48}$$ When $100!$ is expressed in base 12, it terminates in exactly **48 trailing zeros**.Takeaway: Trailing zeros in composite base b = p1^e1 p2^e2 equal min(floor(E pi(N!) / ei)); both prime contributions must be verified.
Example 2.5.6: Positional Counting and Conditional Digit Combinatorics
How many 4-digit positive integers can be formed in base 6 such that no two adjacent digits are identical, and the number is odd?
Show solution
Step 1: Understand base 6 digits and parity.
The digit set is .
-
Even digits: ( digits)
-
Odd digits: ( digits)
An integer in base 6 is odd if and only if its units digit is odd: .
Let the 4-digit number be represented as .
Step 2: Tree analysis by parity of and .
The leading digit cannot be , so ( choices: odd, even).
Adjacent digits cannot be equal: , , and .
Case A: Leading digit is odd (3 choices: )
-
For each odd :
-
is even ( choices: ):
-
is even ( choices) odd ( choices) paths.
-
is odd ( choices) odd and ( choices) paths.
-
-
is odd ( choices):
-
is even ( choices) odd ( choices) paths.
-
is odd ( choices) odd and ( choices) paths.
-
-
-
Total paths for one odd .
-
Total for all 3 odd .
Case B: Leading digit is even (2 choices: )
-
For each even :
-
is even ( choices):
-
is even ( choices) odd ( choices) paths.
-
is odd ( choices) odd and ( choices) paths.
-
-
is odd ( choices):
-
is even ( choices) odd ( choices) paths.
-
is odd ( choices) odd and ( choices) paths.
-
-
-
Total paths for one even .
-
Total for both 2 even .
Step 3: Sum the cases.
There are exactly such numbers in base 6.
Takeaway: When counting base-r numbers with adjacency and parity conditions, split into parity branching paths to handle overlapping digit constraints accurately.
Practice questions
Question 1 · CAT Level
Using standard ternary weights of placed on either pan of a two-pan balance, what is the maximum number of distinct measurable non-zero integer weights up to that can be measured?
Show answer and explanation
Answer: (D) 121
In a two-pan balance, each weight can be placed on the object pan (), the weight pan (), or left unused ().
This corresponds to the balanced ternary representation with trits: weights are with .
The maximum weight is .
Every integer from to has a unique representation in balanced ternary.
Thus, all distinct integer weights up to can be measured.
Question 2 · CAT Level
How many digits does the integer contain when expressed in base ? (Given and )
Show answer and explanation
Answer: (B) 33
The number of digits in base is given by .
Calculate .
Since , we find .
Taking the floor and adding : digits.
Question 3 · CAT Level
How many trailing zeros does have when converted into base ?
Show answer and explanation
Answer: (B) 48
In base , each trailing zero corresponds to a complete factor of .
Highest power of in : .
Thus power of is .
Highest power of in : .
The number of complete factors of is , so there are trailing zeros.
Question 4 · CAT Level
How many three-digit positive integers written in base are palindromes in base ?
Show answer and explanation
Answer: (B) 30
A three-digit number in base has the form .
For to be a valid three-digit number, the leading digit cannot be zero, so ( choices).
The middle digit can be any valid digit in base , so ( choices).
By the fundamental counting principle, total palindromes .
Question 5 · CAT Level
Using standard single-pan binary weights (), an object weighing is weighed. What is the total count of weights placed on the scale pan?
Show answer and explanation
Answer: (B) 5
Single-pan weighing corresponds directly to binary expansion (weights placed correspond to bits set to ).
Convert to binary: .
The number of bits is .
Thus, exactly distinct weights are placed on the pan.
Study this concept with interactive practice in PrepSoc.
Open the concept library