Free CAT library

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 1 kg1\text{ kg} to 40 kg40\text{ kg} 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 wiw_i can have only two states: placed on the pan (11) or left in the cart (00). To weigh all consecutive integers from 11 up to WW, the weights must be the powers of 22:

1,2,4,8,16,32…(Binary!)1, 2, 4, 8, 16, 32 \dots \quad (\text{Binary!})

To cover up to 40 kg40\text{ kg}, he needs 66 weights: {1,2,4,8,16,32}\{1, 2, 4, 8, 16, 32\} (which reach up to 63 kg63\text{ kg}).

But Bachet made a brilliant observation: a balance scale has TWO pans!

You can place a weight on the opposite pan (+1+1), omit it (00), OR place it on the SAME pan as the grain (−1-1, subtracting weight from the other side)!

Because each weight now has THREE distinct states {−1,0,+1}\{-1, 0, +1\}, the optimal weight system is powers of 3 (Balanced Ternary):

1,3,9,27 kg1, 3, 9, 27 \text{ kg}

With just four weights, the merchant can measure every single integer up to:

1+3+9+27=40 kg!1 + 3 + 9 + 27 = 40\text{ kg}!

For instance, to weigh 7 kg7\text{ kg}: place the 9 kg9\text{ kg} weight on the right pan, and the 1 kg1\text{ kg} weight on the left pan with the grain:

Grain+1=9−3+0  ⟹  Grain=9−3+1=7 kg!\text{Grain} + 1 = 9 - 3 + 0 \implies \text{Grain} = 9 - 3 + 1 = 7\text{ kg!}

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:

  1. 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).

  2. Digit Count of Exponential Numbers: How many digits are needed to express 6506^{50} in base 2 or base 36? Solved instantly using ⌊log⁡bN⌋+1\lfloor \log_b N \rfloor + 1.

  3. Trailing Zeros in Base bb: How many trailing zeros does 100!100! have when written in base 12? Solved by prime-factorizing the base (12=22×3112 = 2^2 \times 3^1) and applying Legendre's formula.

  4. Generalized Divisibility Rules: Testing divisibility of a base-rr number by (r−1)(r - 1) (sum of digits) or (r+1)(r + 1) (alternating sum of digits), perfectly generalizing the decimal rules for 9 and 11.

  5. Restricted Digit Combinatorics: Counting how many valid numbers can be formed in base bb under no-consecutive-identical-digits and parity constraints.


3. Core Concepts, Formulae & Derivations

A. The Exact Digit Count Formula

The number of digits Db(N)D_b(N) required to represent a positive integer NN in base bb:

Db(N)=⌊log⁡bN⌋+1D_b(N) = \lfloor \log_b N \rfloor + 1

Equivalence: A number NN requires exactly kk digits in base bb if and only if:

bk−1≤N<bkb^{k-1} \le N < b^k

B. The Single-Pan Weight Theorem (Binary System)

Weights available: {20,21,22,…,2n−1}\{2^0, 2^1, 2^2, \dots, 2^{n-1}\}.

Each weight has coefficient ci∈{0,1}c_i \in \{0, 1\}.

  • Total distinct measurable integer weights: 11 to 2n−12^n - 1.

  • Minimum weights required to weigh any integer up to WW:

    n=⌈log⁡2(W+1)⌉n = \lceil \log_2(W + 1) \rceil

C. The Two-Pan Weight Theorem (Balanced Ternary System)

Weights available: {30,31,32,…,3n−1}\{3^0, 3^1, 3^2, \dots, 3^{n-1}\}.

Each weight has coefficient ci∈{−1,0,+1}c_i \in \{-1, 0, +1\}.

  • Total distinct measurable integer weights: 11 to 3n−12\frac{3^n - 1}{2}.

  • Minimum weights required to weigh any integer up to WW:

    n=⌈log⁡3(2W+1)⌉n = \left\lceil \log_3(2W + 1) \right\rceil

D. The Digital Right-Shift Multiplier Identity

Appending kk zeros to the right of a number in base bb multiplies the number by bkb^k:

(an…a000…0⏟k zeros)b=(an…a0)b×bk(a_n \dots a_0 \underbrace{00\dots0}_{k \text{ zeros}})_b = (a_n \dots a_0)_b \times b^k

Conversely, the number of trailing zeros of NN in base bb equals the largest integer kk such that bk∣Nb^k \mid N.

E. Generalized Radix Divisibility Theorems

For any integer N=(anan−1…a1a0)bN = (a_n a_{n-1} \dots a_1 a_0)_b:

  1. Divisibility by a divisor of bb:

    Since b≡0(modd)b \equiv 0 \pmod d, N≡a0(modd)N \equiv a_0 \pmod d. (Only the last digit matters).

  2. Divisibility by (b−1)(b - 1) (The Generalized '9' Rule):

    Since b≡1(modb−1)b \equiv 1 \pmod{b - 1}, bi≡1i≡1(modb−1)b^i \equiv 1^i \equiv 1 \pmod{b - 1}:

    N≡∑i=0nai(modb−1)N \equiv \sum_{i=0}^n a_i \pmod{b - 1}

    NN is divisible by (b−1)(b - 1) if and only if the sum of its base-bb digits is divisible by (b−1)(b - 1).

  3. Divisibility by (b+1)(b + 1) (The Generalized '11' Rule):

    Since b≡−1(modb+1)b \equiv -1 \pmod{b + 1}, bi≡(−1)i(modb+1)b^i \equiv (-1)^i \pmod{b + 1}:

    N≡∑i=0n(−1)iai=(a0−a1+a2−a3+… )(modb+1)N \equiv \sum_{i=0}^n (-1)^i a_i = (a_0 - a_1 + a_2 - a_3 + \dots) \pmod{b + 1}

    NN is divisible by (b+1)(b + 1) if and only if the alternating sum of its base-bb digits is divisible by (b+1)(b + 1).


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 N!N! in base 12, students often test 12 directly. But 12 is composite (12=22×312 = 2^2 \times 3).

You must compute the count of prime factor 22 (halved, since 22=42^2 = 4) and prime factor 33, then take the minimum!

[!TIP]

Digit Count for Powers of the Base:

Any exact power bkb^k has exactly k+1k + 1 digits in base bb (a leading 11 followed by kk zeros).

For example, 28=2562^8 = 256 has 8+1=98 + 1 = 9 bits (100000000_2).

Formulas

Exact Radix Digit Count

Db(N)=⌊log⁡bN⌋+1D_b(N) = \lfloor \log_b N \rfloor + 1

Number of digits needed to represent positive integer N in radix b
Single-Pan Binary Weight Capacity

Wmax⁡=2n−1  ⟹  n=⌈log⁡2(W+1)⌉W_{\max} = 2^n - 1 \implies n = \lceil \log_2(W + 1) \rceil

Coefficients in {0, 1}; weights are powers of 2 (1, 2, 4, 8, ...)
Two-Pan Balanced Ternary Capacity

Wmax⁡=3n−12  ⟹  n=⌈log⁡3(2W+1)⌉W_{\max} = \frac{3^n - 1}{2} \implies n = \lceil \log_3(2W + 1) \rceil

Coefficients in {-1, 0, +1}; weights are powers of 3 (1, 3, 9, 27, ...)
Generalized (b - 1) Divisibility

(N)b≡∑i=0nai(modb−1)(N)_b \equiv \sum_{i=0}^n a_i \pmod{b - 1}

Generalizes base-10 divisibility by 9 to the sum of digits in radix b
Generalized (b + 1) Divisibility

(N)b≡∑i=0n(−1)iai(modb+1)(N)_b \equiv \sum_{i=0}^n (-1)^i a_i \pmod{b + 1}

Generalizes base-10 divisibility by 11 to alternating digit sum in radix b

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 N=650N = 6^{50} in: (a) base 6, (b) base 36, and (c) binary (base 2)? (Given log⁡102≈0.3010\log_{10} 2 \approx 0.3010 and log⁡103≈0.4771\log_{10} 3 \approx 0.4771).

Show solution

Part (a): In Base 6

N=650N = 6^{50} is an exact power of the base 66.

In base 6, 6506^{50} is represented as 11 followed by exactly 5050 zeros:

(650)6=(100…0⏟50 zeros)6(6^{50})_6 = (1\underbrace{00\dots0}_{50 \text{ zeros}})_6

Total Digits=50+1=51 digits\text{Total Digits} = 50 + 1 = \mathbf{51 \text{ digits}}

Part (b): In Base 36

Express NN as a power of 3636:

36=62  ⟹  N=650=(62)25=362536 = 6^2 \implies N = 6^{50} = (6^2)^{25} = 36^{25}

In base 36, 362536^{25} is represented as 11 followed by 2525 zeros:

Total Digits=25+1=26 digits\text{Total Digits} = 25 + 1 = \mathbf{26 \text{ digits}}

Part (c): In Binary (Base 2)

Apply the logarithmic digit formula:

D2(N)=⌊log⁡2(650)⌋+1=⌊50log⁡26⌋+1D_2(N) = \lfloor \log_2(6^{50}) \rfloor + 1 = \lfloor 50 \log_2 6 \rfloor + 1

Convert log⁡26\log_2 6 using change of base:

log⁡26=log⁡106log⁡102=log⁡102+log⁡103log⁡102=1+log⁡103log⁡102\log_2 6 = \frac{\log_{10} 6}{\log_{10} 2} = \frac{\log_{10} 2 + \log_{10} 3}{\log_{10} 2} = 1 + \frac{\log_{10} 3}{\log_{10} 2}

Substitute the given values:

0.47710.3010≈1.58505  ⟹  log⁡26≈1+1.58505=2.58505\frac{0.4771}{0.3010} \approx 1.58505 \implies \log_2 6 \approx 1 + 1.58505 = 2.58505

Multiply by 5050:

50×2.58505=129.252550 \times 2.58505 = 129.2525

Take the floor and add 11:

D2(N)=⌊129.2525⌋+1=129+1=130 bitsD_2(N) = \lfloor 129.2525 \rfloor + 1 = 129 + 1 = \mathbf{130 \text{ bits}}

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 1 gram1\text{ gram} to 100 grams100\text{ grams}. 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 wiw_i can be either used (11) or omitted (00).

With nn weights, the maximum measurable weight is the sum of geometric powers of 22:

Wmax⁡=20+21+22+⋯+2n−1=2n−1W_{\max} = 2^0 + 2^1 + 2^2 + \dots + 2^{n-1} = 2^n - 1

Set Wmax⁡≥100W_{\max} \ge 100:

2n−1≥100  ⟹  2n≥1012^n - 1 \ge 100 \implies 2^n \ge 101

Since 26=64<1012^6 = 64 < 101 and 27=128≥1012^7 = 128 \ge 101:

n=7 weightsn = \mathbf{7 \text{ weights}}

Weight set: {1,2,4,8,16,32,64} grams\{1, 2, 4, 8, 16, 32, 64\}\text{ grams} (total capacity =127 g= 127\text{ g}).

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 (5a34)8(5a34)_8, where aa is an unknown digit. If this number is known to be exactly divisible by 77, determine all possible values of the digit aa.

Show solution

Step 1: Apply the generalized (b−1)(b - 1) divisibility theorem.

Here the base is b=8b = 8, and the divisor is b−1=8−1=7b - 1 = 8 - 1 = 7.

Since 8≡1(mod7)8 \equiv 1 \pmod 7, we have 8k≡1k≡1(mod7)8^k \equiv 1^k \equiv 1 \pmod 7 for all powers k≥0k \ge 0.

Therefore, any base-8 number is congruent to the sum of its digits modulo 7:

(5a34)8≡5+a+3+4(mod7)(5a34)_8 \equiv 5 + a + 3 + 4 \pmod 7

Step 2: Simplify the congruence.

5+a+3+4=12+a5 + a + 3 + 4 = 12 + a

Reduce 1212 modulo 7:

12=1×7+5  ⟹  12+a≡5+a(mod7)12 = 1 \times 7 + 5 \implies 12 + a \equiv 5 + a \pmod 7

Step 3: Solve for divisibility by 7.

For (5a34)8(5a34)_8 to be divisible by 7:

5+a≡0(mod7)  ⟹  a≡−5≡2(mod7)5 + a \equiv 0 \pmod 7 \implies a \equiv -5 \equiv 2 \pmod 7

Step 4: Filter against allowable base-8 digits.

In base 8, the allowable digits are Σ8={0,1,2,3,4,5,6,7}\Sigma_8 = \{0, 1, 2, 3, 4, 5, 6, 7\}.

The only digit satisfying a≡2(mod7)a \equiv 2 \pmod 7 in this set is:

a=2a = \mathbf{2}

Verification:

For a=2a = 2, (5234)8=5(512)+2(64)+3(8)+4=2,560+128+24+4=2,71610(5234)_8 = 5(512) + 2(64) + 3(8) + 4 = 2,560 + 128 + 24 + 4 = 2,716_{10}.

Check divisibility: 2,716÷7=3882,716 \div 7 = 388 (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 (52413)6(52413)_6 is divisible by 77. If not, find its remainder when divided by 77.

Show solution

Step 1: Apply the generalized (b+1)(b + 1) divisibility theorem.

Here the radix is b=6b = 6, and the divisor is b+1=6+1=7b + 1 = 6 + 1 = 7.

Notice that 6≡−1(mod7)6 \equiv -1 \pmod 7.

Therefore, powers of the base alternate in sign modulo 7:

60≡+1,61≡−1,62≡+1,63≡−1,64≡+1(mod7)6^0 \equiv +1, \quad 6^1 \equiv -1, \quad 6^2 \equiv +1, \quad 6^3 \equiv -1, \quad 6^4 \equiv +1 \pmod 7

Step 2: Compute the alternating sum of digits.

Multiply digits by alternating signs starting with +1+1 at the units place (606^0):

Salt=(+1)⋅3+(−1)⋅1+(+1)⋅4+(−1)⋅2+(+1)⋅5S_{\text{alt}} = (+1) \cdot 3 + (-1) \cdot 1 + (+1) \cdot 4 + (-1) \cdot 2 + (+1) \cdot 5

Salt=3−1+4−2+5=9S_{\text{alt}} = 3 - 1 + 4 - 2 + 5 = 9

Step 3: Evaluate modulo 7.

9=1×7+2  ⟹  Salt≡2(mod7)9 = 1 \times 7 + 2 \implies S_{\text{alt}} \equiv 2 \pmod 7

Since the alternating sum is not congruent to 0(mod7)0 \pmod 7, (52413)6(52413)_6 is not divisible by 7.

Its remainder upon division by 7 is 2\mathbf{2}.

Verification via Decimal:

(52413)6=5(1,296)+2(216)+4(36)+1(6)+3=6,480+432+144+6+3=7,06510(52413)_6 = 5(1,296) + 2(216) + 4(36) + 1(6) + 3 = 6,480 + 432 + 144 + 6 + 3 = 7,065_{10}

7,065÷7=1,009with remainder 27,065 \div 7 = 1,009 \quad \text{with remainder } \mathbf{2}

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 N=100!N = 100! is written in duodecimal notation (base 12).

Show solution

Step 1: Understand trailing zeros in a base.

The number of trailing zeros of NN in base bb is the highest power kk such that bk∣Nb^k \mid N.

Step 2: Prime factorize the base b=12b = 12.

12=22×3112 = 2^2 \times 3^1

To form one factor of 1212, we require two factors of 22 and one factor of 33.

Therefore:

k=min⁡(⌊E2(100!)2⌋,  E3(100!))k = \min\left( \left\lfloor \frac{E_2(100!)}{2} \right\rfloor, \; E_3(100!) \right)

where Ep(100!)E_p(100!) is the exponent of prime pp in 100!100! given by Legendre's formula.

Step 3: Compute E2(100!)E_2(100!) 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 Σ6={0,1,2,3,4,5}\Sigma_6 = \{0, 1, 2, 3, 4, 5\}.

  • Even digits: {0,2,4}\{0, 2, 4\} (33 digits)

  • Odd digits: {1,3,5}\{1, 3, 5\} (33 digits)

An integer in base 6 is odd if and only if its units digit is odd: d0∈{1,3,5}d_0 \in \{1, 3, 5\}.

Let the 4-digit number be represented as d3d2d1d0d_3 d_2 d_1 d_0.

Step 2: Tree analysis by parity of d3d_3 and d1d_1.

The leading digit d3d_3 cannot be 00, so d3∈{1,2,3,4,5}d_3 \in \{1, 2, 3, 4, 5\} (55 choices: 33 odd, 22 even).

Adjacent digits cannot be equal: d3≠d2d_3 \ne d_2, d2≠d1d_2 \ne d_1, and d1≠d0d_1 \ne d_0.

Case A: Leading digit d3d_3 is odd (3 choices: {1,3,5}\{1, 3, 5\})

  • For each odd d3d_3:

    • d2d_2 is even (33 choices: {0,2,4}\{0, 2, 4\}):

      • d1d_1 is even (3−1=23 - 1 = 2 choices)   ⟹  d0\implies d_0 odd (33 choices)   ⟹  3×2×3=18\implies 3 \times 2 \times 3 = 18 paths.

      • d1d_1 is odd (33 choices)   ⟹  d0\implies d_0 odd and ≠d1\ne d_1 (3−1=23 - 1 = 2 choices)   ⟹  3×3×2=18\implies 3 \times 3 \times 2 = 18 paths.

    • d2d_2 is odd (3−1=23 - 1 = 2 choices):

      • d1d_1 is even (33 choices)   ⟹  d0\implies d_0 odd (33 choices)   ⟹  2×3×3=18\implies 2 \times 3 \times 3 = 18 paths.

      • d1d_1 is odd (3−1=23 - 1 = 2 choices)   ⟹  d0\implies d_0 odd and ≠d1\ne d_1 (22 choices)   ⟹  2×2×2=8\implies 2 \times 2 \times 2 = 8 paths.

  • Total paths for one odd d3=18+18+18+8=62d_3 = 18 + 18 + 18 + 8 = 62.

  • Total for all 3 odd d3=3×62=186d_3 = 3 \times 62 = \mathbf{186}.

Case B: Leading digit d3d_3 is even (2 choices: {2,4}\{2, 4\})

  • For each even d3d_3:

    • d2d_2 is even (3−1=23 - 1 = 2 choices):

      • d1d_1 is even (22 choices)   ⟹  d0\implies d_0 odd (33 choices)   ⟹  2×2×3=12\implies 2 \times 2 \times 3 = 12 paths.

      • d1d_1 is odd (33 choices)   ⟹  d0\implies d_0 odd and ≠d1\ne d_1 (22 choices)   ⟹  2×3×2=12\implies 2 \times 3 \times 2 = 12 paths.

    • d2d_2 is odd (33 choices):

      • d1d_1 is even (33 choices)   ⟹  d0\implies d_0 odd (33 choices)   ⟹  3×3×3=27\implies 3 \times 3 \times 3 = 27 paths.

      • d1d_1 is odd (22 choices)   ⟹  d0\implies d_0 odd and ≠d1\ne d_1 (22 choices)   ⟹  3×2×2=12\implies 3 \times 2 \times 2 = 12 paths.

  • Total paths for one even d3=12+12+27+12=63d_3 = 12 + 12 + 27 + 12 = 63.

  • Total for both 2 even d3=2×63=126d_3 = 2 \times 63 = \mathbf{126}.

Step 3: Sum the cases.

Total Valid Numbers=186+126=312\text{Total Valid Numbers} = 186 + 126 = \mathbf{312}

There are exactly 312312 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 1 kg,3 kg,9 kg,27 kg,81 kg1\text{ kg}, 3\text{ kg}, 9\text{ kg}, 27\text{ kg}, 81\text{ kg} placed on either pan of a two-pan balance, what is the maximum number of distinct measurable non-zero integer weights up to 121 kg121\text{ kg} that can be measured?

  1. A

    6060

  2. B

    8181

  3. C

    120120

  4. D

    121121

Show answer and explanation

Answer: (D) 121

In a two-pan balance, each weight can be placed on the object pan (−1-1), the weight pan (+1+1), or left unused (00).

This corresponds to the balanced ternary representation with 55 trits: weights are ∑i=04ci3i\sum_{i=0}^4 c_i 3^i with ci∈{−1,0,1}c_i \in \{-1, 0, 1\}.

The maximum weight is ∑i=043i=35−12=2422=121 kg\sum_{i=0}^4 3^i = \frac{3^5 - 1}{2} = \frac{242}{2} = 121\text{ kg}.

Every integer from 11 to 121121 has a unique representation in balanced ternary.

Thus, all 121121 distinct integer weights up to 121 kg121\text{ kg} can be measured.

Question 2 · CAT Level

How many digits does the integer N=250×520N = 2^{50} \times 5^{20} contain when expressed in base 88? (Given log⁡102≈0.3010\log_{10} 2 \approx 0.3010 and log⁡105≈0.6990\log_{10} 5 \approx 0.6990)

  1. A

    3232

  2. B

    3333

  3. C

    3434

  4. D

    3535

Show answer and explanation

Answer: (B) 33

The number of digits in base 88 is given by ⌊log⁡8N⌋+1=⌊log⁡10Nlog⁡108⌋+1\lfloor \log_8 N \rfloor + 1 = \lfloor \frac{\log_{10} N}{\log_{10} 8} \rfloor + 1.

Calculate log⁡10N=50log⁡102+20log⁡105=50(0.3010)+20(0.6990)=15.050+13.980=29.030\log_{10} N = 50 \log_{10} 2 + 20 \log_{10} 5 = 50(0.3010) + 20(0.6990) = 15.050 + 13.980 = 29.030.

Since log⁡108=3log⁡102=3(0.3010)=0.9030\log_{10} 8 = 3 \log_{10} 2 = 3(0.3010) = 0.9030, we find log⁡8N=29.0300.9030≈32.148\log_8 N = \frac{29.030}{0.9030} \approx 32.148.

Taking the floor and adding 11: ⌊32.148⌋+1=32+1=33\lfloor 32.148 \rfloor + 1 = 32 + 1 = 33 digits.

Question 3 · CAT Level

How many trailing zeros does (100!)10(100!)_{10} have when converted into base 1212?

  1. A

    2424

  2. B

    4848

  3. C

    4949

  4. D

    9797

Show answer and explanation

Answer: (B) 48

In base 12=22×312 = 2^2 \times 3, each trailing zero corresponds to a complete factor of 1212.

Highest power of 22 in 100!100!: ⌊100/2⌋+⌊100/4⌋+⌊100/8⌋+⌊100/16⌋+⌊100/32⌋+⌊100/64⌋=50+25+12+6+3+1=97\lfloor 100/2 \rfloor + \lfloor 100/4 \rfloor + \lfloor 100/8 \rfloor + \lfloor 100/16 \rfloor + \lfloor 100/32 \rfloor + \lfloor 100/64 \rfloor = 50 + 25 + 12 + 6 + 3 + 1 = 97.

Thus power of 222^2 is ⌊97/2⌋=48\lfloor 97/2 \rfloor = 48.

Highest power of 33 in 100!100!: ⌊100/3⌋+⌊100/9⌋+⌊100/27⌋+⌊100/81⌋=33+11+3+1=48\lfloor 100/3 \rfloor + \lfloor 100/9 \rfloor + \lfloor 100/27 \rfloor + \lfloor 100/81 \rfloor = 33 + 11 + 3 + 1 = 48.

The number of complete factors of 1212 is min⁡(48,48)=48\min(48, 48) = 48, so there are 4848 trailing zeros.

Question 4 · CAT Level

How many three-digit positive integers written in base 66 are palindromes in base 66?

  1. A

    2525

  2. B

    3030

  3. C

    3636

  4. D

    4242

Show answer and explanation

Answer: (B) 30

A three-digit number in base 66 has the form (aba)6(aba)_6.

For (aba)6(aba)_6 to be a valid three-digit number, the leading digit aa cannot be zero, so a∈{1,2,3,4,5}a \in \{1, 2, 3, 4, 5\} (55 choices).

The middle digit bb can be any valid digit in base 66, so b∈{0,1,2,3,4,5}b \in \{0, 1, 2, 3, 4, 5\} (66 choices).

By the fundamental counting principle, total palindromes =5×6=30= 5 \times 6 = 30.

Question 5 · CAT Level

Using standard single-pan binary weights (1 g,2 g,4 g,8 g,16 g,32 g,64 g,128 g1\text{ g}, 2\text{ g}, 4\text{ g}, 8\text{ g}, 16\text{ g}, 32\text{ g}, 64\text{ g}, 128\text{ g}), an object weighing 179 grams179\text{ grams} is weighed. What is the total count of weights placed on the scale pan?

  1. A

    44

  2. B

    55

  3. C

    66

  4. D

    77

Show answer and explanation

Answer: (B) 5

Single-pan weighing corresponds directly to binary expansion (weights placed correspond to bits set to 11).

Convert 179179 to binary: 179=128+32+16+2+1=(10110011)2179 = 128 + 32 + 16 + 2 + 1 = (10110011)_2.

The number of 11 bits is 1+1+1+1+1=51 + 1 + 1 + 1 + 1 = 5.

Thus, exactly 55 distinct weights are placed on the pan.

Study this concept with interactive practice in PrepSoc.

Open the concept library