The Handshakes Problem: Formula, Derivation, and Code

Given n people in a room where everyone shakes hands exactly once with every other person, the total handshakes always equal n*(n-1)/2.

Why This Problem Appears in Placement Aptitude Rounds

Combinatorics questions are a staple of the quantitative aptitude section in campus placement evaluation tests. Test designers favour them for two reasons: the underlying logic is not difficult, but students who have only memorised a formula stumble on the variants.

The handshakes problem is one of the cleanest combinatorics setups. Everyone shakes hands with everyone else. No pair repeats. No one shakes their own hand. The question is just: how many distinct pairs can you form from n people?

A student who has only memorised n*(n-1)/2 will answer the standard question correctly. But placement test variants often swap the wording: “10 teams, round-robin matches” or “8 delegates, each introduced to every other.” A student who understands the derivation recognises the pattern in three seconds; a student who memorised the formula has to decide if the variant is “the same type.” Derivation-first beats formula-first every time in this topic.

Placement test question banks use the same combinatorial structure for:

• Maximum handshakes in a room
• Total matches in a round-robin tournament
• Number of direct network connections between n devices
• Total meetings at a conference where every delegate meets every other delegate once

All four reduce to n*(n-1)/2. Understanding the derivation, not just the formula, means you recognise the variant instantly in the exam.

The quantitative aptitude section of most off-campus placement tests covers combinatorics and permutations in every test version. Knowing n*(n-1)/2 cold, including at least one worked variant, is a reliable point-saver.

Deriving the Formula from First Principles

Two independent derivation paths both arrive at the same formula. Knowing either one is enough for an exam; knowing both makes the variants obvious.

Derivation 1: Arithmetic Series

Label the people P1, P2, P3, …, Pn.

• P1 shakes hands with P2, P3, …, Pn — that is n-1 handshakes.
• P2 has already shaken with P1. P2 shakes with P3, P4, …, Pn — that is n-2 handshakes.
• P3 has already shaken with P1 and P2. P3 shakes with P4, …, Pn — that is n-3 handshakes.
• This continues until P(n-1) shakes with Pn — 1 handshake.
• Pn has already shaken with everyone — 0 remaining.

Total = (n-1) + (n-2) + ... + 2 + 1

This is the sum of the first (n-1) positive integers. The Gaussian formula gives the sum of the first m positive integers as m*(m+1)/2. Setting m = n-1:

Total = (n-1)*n/2 = n*(n-1)/2

The classic Gaussian pairing argument shows why: write the sum forwards and backwards on two rows, then add column by column. Every column sums to n (the first term plus the last, the second plus the second-to-last, and so on). There are (n-1) columns, so the doubled sum is n*(n-1). Divide by 2 to get the actual total: n*(n-1)/2.

Derivation 2: Combinations

A handshake is a unique, unordered pair of people. Choosing 2 people from n (where the order of selection does not matter) is precisely the combination C(n,2).

Expanding the combination formula:

C(n,2) = n! / (2! × (n-2)!)

Cancel (n-2)! from numerator and denominator:

= n × (n-1) × (n-2)! / (2 × (n-2)!)

= n × (n-1) / 2

= n*(n-1)/2

Both paths confirm the same formula. Khan Academy’s combinations section covers the general combination formula with additional interactive examples if you want more practice with the derivation steps.

Worked Examples with Verification

n = 4

• Formula: 4*(4-1)/2 = 4*3/2 = 12/2 = 6
• Enumeration check: with people A, B, C, D, the distinct pairs are AB, AC, AD, BC, BD, CD — exactly 6. ✓

n = 10

• Formula: 10*(10-1)/2 = 10*9/2 = 90/2 = 45
• Total: 45 handshakes.

n = 15

• Formula: 15*(15-1)/2 = 15*14/2 = 210/2 = 105
• Total: 105 handshakes.

The enumeration check for n=4 is worth doing once with pen and paper. Listing all pairs manually takes under two minutes and makes the double-counting argument concrete: you see that AB and BA would be the same handshake, which is why dividing by 2 is correct.

For large n, enumeration is impractical. That is precisely where the formula earns its place. Verifying n=4 by enumeration, then trusting the formula for n=15 or n=100, is the right workflow: small-case check first, formula application second.

Algorithm and Implementation

The formula is O(1): no loops, no recursion. Input n, compute n*(n-1)/2, print the result.

Python

def max_handshakes(n):
    return n * (n - 1) // 2

n = int(input())
print(max_handshakes(n))

Integer floor division (//) avoids any floating-point drift. Since n*(n-1) always includes one even factor (consecutive integers), the division by 2 is exact.

C

#include <stdio.h>

int main() {
    long long n;
    scanf("%lld", &n);
    long long result = n * (n - 1) / 2;
    printf("%lld\n", result);
    return 0;
}

Use long long rather than int when n could be large. For very large inputs, n*(n-1) overflows a 32-bit signed integer before the division, so the wider type avoids silent truncation.

Sample run:

Input:  15
Output: 105

Common Variants in Aptitude Tests

The same n*(n-1)/2 structure appears in several standard question types.

Round-Robin Tournament

n teams each play every other team exactly once. Total matches = n*(n-1)/2. For 6 teams: 6*5/2 = 15 matches.

Network Connections

n devices in a network, each connected directly to every other device. Total connections = n*(n-1)/2. In graph theory, this is the number of edges in a complete graph on n nodes.

Conference Introductions

Every delegate at a conference introduces themselves to every other delegate. Total introductions = n*(n-1)/2. This is the exact same model as the original handshakes problem.

The variant that trips students up is when the problem adds a constraint, such as “each person only shakes hands with the three people nearest to them.” That breaks the complete-graph assumption and the formula no longer applies directly. If the problem does not restrict who meets whom, n*(n-1)/2 is the answer.

When the Formula Does Not Apply

Watch for constraint language: “each person meets at most k others”, “only adjacent teams play”, “pairs within the same group only.” Any restriction on which pairs can form means you cannot use n*(n-1)/2 for the whole group. In those cases, re-derive from the constraint rather than reach for the shortcut.

Practice Questions

Work through these before your next aptitude round.

• Q1: 8 people attend a meeting. Each person shakes hands with every other person exactly once. How many handshakes in total?

  • Answer: 8*(8-1)/2 = 8*7/2 = 56/2 = 28 handshakes.

• Q2: A league has 7 cricket teams. Each team plays every other team once. How many matches are scheduled?

  • Answer: 7*(7-1)/2 = 7*6/2 = 42/2 = 21 matches.

• Q3: 20 delegates attend a summit. Each delegate meets every other delegate. How many total meetings?

  • Answer: 20*(20-1)/2 = 20*19/2 = 380/2 = 190 meetings.

• Q4: A network has 12 nodes, each connected to every other node. How many direct connections exist?

  • Answer: 12*(12-1)/2 = 12*11/2 = 132/2 = 66 connections.

For more structured practice across the full quantitative aptitude syllabus, placement preparation books that cover the permutations and combinations chapter are the fastest way to lock in variant recognition before a placement drive.

The complete-graph structure that n*(n-1)/2 describes, every node connected to every other node, is also the topology inside a transformer’s self-attention layer, where each of n tokens attends to all other tokens in the sequence. TinkerLLM is a low-cost entry point to build with that structure in working code, at ₹299.