Hanger Party!

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Hanger Party!

G H J

Reveal topic tags

olympic revenge 2002

olympic revenge

L

G H BBookmark kLocked kLocked NReply

Source: I Brazilian Olympic Revenge 2002, Problem 5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Johann Peter Dirichlet

376 posts

Johann Peter Dirichlet

#1 h Apr 26, 2015, 5:32 PM • 1 Y

Y by Adventure10

In a "Hanger Party", the guests are initially dressed. In certain moments, the host chooses a guest, and the chosen guest and all his friends will wear its respective clothes if they are naked, and undress it if they are dressed.

It is possible that, in some moment, the guests are naked, independent of their mutual friendships? (Suppose friendship is reciprocal.)

This post has been edited 1 time. Last edited by Johann Peter Dirichlet, Jun 5, 2015, 12:20 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2460 posts

#2 h May 2, 2015, 5:26 PM • 3 Y

Y by Math_CYCR, Adventure10, Mango247

Yes, it's possible.
Let $G$ be the graph representing friendships between guests. It's convenient to consider each vertex to be connected with itself(by a loop).
The problem boils down to find a subset of vertices $V'$ of $G$ , with the property: Every vertex $v$ of $G$ is connected with odd number of vertices of $V'$ .
Let $A=(a_ij)\,,\,i,j=1,2,\dots,n$ be the adjacency matrix of $G$ . Translated in the linear algebra language it sounds like:

Claim: Let $A=(a_{ij})\,,\,i,j=1,2,\dots,n$ be $n\times n$ symmetric matrix over $\mathbb{F}_2$ with $a_{ii}=1\,,\,i=1,2,\dots,n$ . Then, there exists a subset of rows of $A$ , which sum is $(1,1,\dots,1)$ .
Proof. If the rank of $A$ is $n$ then all rows of $A$ are a basis (as vectors over $\mathbb{F}_2$ ) and some linear combination of them will be $(1,1,\dots,1)$ . Suppose the rank of $A$ is $m<n$ . WLOG suppose the first $m$ rows $v_1,v_2,\dots,v_m$ are linearly independent and any other row is a linear combination (over $\mathbb{F}_2$ ) of them. Thus, there exist $1\leq m_1<m_2<\dots<m_k\leq m$ , such that the first $m$ coordinates of $v=\sum_{I=1}^k v_{m_i}$ are all $1$ s. We will prove the other coordinates of $v$ are also $1$ s. Let $v_j\,,\,j>m$ is the $j$ -th row. Since it's a linear combination of the first $m$ rows, we have $v_j=\sum_{i=1}^{r}v_{j_i}\,\,,\, j_i\leq m$ . Note that $r$ must be odd. Indeed, since $A$ is symmetric, $j$ -th column is also sum of all $j_1,j_2,\dots,j_r$ columns. Further, $a_{jj}$ must be $1$ , and it is equal to a sum of $r$ number of $1$ s and sum of all $a_{j_p j_q}\,,j_p\neq j_q$ . Since $A$ is symmetric, the latter is $0$ , implying $r$ is odd.

Now, $j$ -th column is a sum of $j_1,j_2,\dots$ and $j_r$ -th columns. In each of these columns, the sum of its $m_1,m_2,\dots, m_k$ coordinates is $1$ , therefore the sum of $m_1,m_2,\dots, m_k$ coordinates of the $j$ -th column is also $1$ .
Thus, we proved, $v_{m_1}+\dots + v_{m_k}=1$ ,

This post has been edited 1 time. Last edited by dgrozev, May 2, 2015, 5:28 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1519 posts

#3 h Nov 18, 2023, 4:12 AM

Y by

This is also a problem from Germany TST 2004.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a